Might be worth posting some more data on the mp3s, e.g. are they vbr, or an odd bitrate, etc.?

I've certainly not had any troubles with the handful of mp3s I've played.