One of three things I can think of.
1. Bad copy of the song in the iPod. Occasionally a sync goes bad and songs are corrupted as they copied to the iPod. Remove the songs from the iPod and put them back on.
2. Songs are marked Skip On Shuffle and you are using Shuffle turned on with the iPod and not with iTunes.
3. Song encoding is PC specific and not iPod compatible (MP4 video format on an audio only iPod). You can find the song in your iTunes Library, right click it and choose Create AAC Version (if your import settings are set to iTunes format) or Create MP3 Version (if your import settings are set to MP3 format) to get a version that is iPod compatible. Remove the old version of the song from the iPod and put the new one on.