Hey there.
I have been searching for at least 6 months for a problem to this issue.
The issue is that mp3s that are not properly encoded cause the newer ipod classics to skip the song or incorrectly play it. This predominantly occurs with vbr encoded mp3s. It is weird as they play with no problem on the iphone and shuffle.
Anyways, I am happy to report a 100% solution to this problem.
Go to
http://mp3val.sourceforge.net/ and download the mp3val software.
Extract it from the archive and repair all your mp3's through it and re-sync your ipod. From this point all the problematic mp3s should work with out issue.
Please note, that this software is windows only.
What i did was actually enable disk mode and repaired the mp3's directly on the ipod classic (120gb model), it took a few hours to repair about 10K of mp3s.
Hopefully this fix should work for you.
Cheers
Ajay