I get this a lot with MP3s and it is because of the chips that Apple used in these iPods. It's only in the very latest ones they have solved this by using a different manufacturer. The best way I found to solve this was convert all the MP3s to AAC.
To do this, in iTunes
- go to the preferences and in the General section where it says 'When I insert a CD' or similar there is an ImportSettings button. Click this and in here there is a selector for 'ImportUsing' and change it to AAC - The native codec for the iPod. Save all this
- then in the main music library select the song you want to repair and right-click (ctrl-click on a mac) then choose 'Create AAC Version'. This will convert it.
- Now right click it and choose 'Show in Explorer' (Finder on a Mac) and delete the MP3 version.
- Back in iTunes if it made duplicate listings for the song try to play it. If it plays that's the AAC version if it doesn't thats the old MP3 version and needs deleting.
- Transfer the AAC version into any Playlists you had associated with it for the iPod.
Kind of a pain if you've got loads of them to do but it does work. I tried repairing the mp3s in other software but the ipod still had issues with them so AAC is the way to go. (You can also convert them back to MP3 from the AACs which also fixes it but if you haven't transfered the AACs to the iPod it wont recognise the change of file for the MP3s)
Hope this helps you out.
All the best