Most music-player apps utilize Android's built-in music-playing functionality (known as a "library") but Android doesn't natively support all music file types. Though Android's library supports MP3 playback, it's possible that your MP3 files are corrupted or that the codec used to create some of the MP3 files isn't compatible with Android's playback libraries. (E.g. I had a problem where Android could can play most of my WMA music files but not the ones that were created on a different computer with a certain WMA codec. Those WMA files played properly on PCs, car stereos, etc. but not on all Android apps.)
A few of the Android player apps, like PowerAmp, have their own supplemental libraries for playback of unsupported file types but I'd guess that PowerAmp uses Android's library to play MP3 files. You'd have to try each one to know for sure. I don't know which ones even have their own libraries.
It may be worth noting that each time you transcode from one "lossy" compression format to another (e.g. WMA-to-MP3) or even if you just recompress MP3-to-MP3, you'll lose some audio fidelity. (Personally, I refuse to do such conversion of lossy music files, but I'm fussy like that.)