Greetings!

You rang???

I have had the problem with audiobooks, but I use VBR files and attribute it to the lack of Xing header.

Constant bit rate... Hmm... A thought: have you tried to compress another file down to that bit rate to see if it is the bit rate vs. the files themselves? Have any kind of MP3 diagnostic utilities shown any problems with the files themselves?