Mixxx is especially sensitve to MP3 frame errors, and from what you said, it sounds like there were alot of them in the original files. Re-encoding with a quality encoder will reduce the frequency of such errors and allow the tracks to play better in Mixxx. Normally though, if songs of any file type play too slowly, then it's a latency issue as RJ said.
Mixxx Developer - Controller Specialist
Mixxx Windows package maintainer