I'd guess that you have either a corrupted database on your iPod or a flakey hard drive.
In general, regardless of the version of MC, when I've got a iPod giving me trouble I try these tactics:
First, you can google for the maintenance mod on the iPod. When you get it into Maintenance mode, you can do a test of the hard drive.
Next, if it passes that test, I'd probably try restoring the iPod from iTunes. That recreates a blank database. Of course, you'll have to resync everything and that could take a long time depending on how full your iPod is...