The first thing you should do is hook up the iPod to your computer, open up iTunes, wait for the syncing operation to complete, then click on the restore button in the device window. That will return the iPod to the original factory state (Note, all songs/podcasts/videos/etc will be lost and have to be reloaded, make sure you are ready to do this time-wise as well as have all files).
If that does not work, select up the update button in the update window. That should install any new firmware that is needed.