Have you tried resetting the iPod? Just press and hold the Play and Menu buttons until the Apple logo screen comes up, and it should do fine.
If that doesn't work, you could try reinstalling the latest iPod software. Sometimes they get stuck in a glitch state (sorry for the technical term there!) and reinstalling the software forces the iPod to hard boot from freshly loaded (and thus clean) code.