If your MP3s were encoded using a different ripper/encoder than iTunes, there may be embedded icon data stored inside the MP3 file.
This can cause iPod to read beyond the actual end of the music data, where it will read a portion of another song.
Read AppleCare Knowledge Base document #61638 for more information and suggested solutions.