If the problem goes away when you recode, it may be worthwhile to check the files for integrity first.
You find a section in the HowTos showing links to tools:
It’s required and often helps to reduce support cycles to check files for errors before filing a bug report.
Symptoms of erroneous files are often
missing or wrong bitrate or length
audible blips or skips
tags seem to be sticky and cannot be removed
There are some really good tools to check the files for errors, namely
MP3 Diags — identifies many different issues in MP3 files
Website: http://mp3diags.sourceforge.net
Download: MP3 Diags - Getting MP3 Diags
If the font size in MP3 Diags is …