Mine started skipping through iTMS songs a few weeks ago and randomly freezing. Resetting it (turning to hold/on, then pressing down select/menu together) worked briefly but problems recurred.
In the end, I restored it and it started working properly again. Plug the iPod in, close iTunes and then run the iPod installer (you can download it if you've misplaced it) and tell it you want to restore it to factory defaults. It does mean that you'll lose all your music/data on the iPod and have to transfer it all back over but it worked for me.