Usually if an iPod is acting weird, resetting it will fix it.
With my ipod (all white face, four buttons along the top), you press and hold the menu and play buttons for a few seconds.
I think with the new ones, you press and hold menu and the round button in the middle of the scroll pad.
Resetting doesn't erase anything, it just reboots the system or whatever.
Also, try reconnecting it to iTunes, remove the songs and put them back on, like call it glitter said (if you're doing automatic syncing, make sure you don't throw out the songs permanently!)