Well, I agree with you that it looks more and more like a hardware issue related exclusively to the MP3 player. It's kind of a long shot, but have you tried:
- Having the MP3 player connected to the +5V and GND, buit not to the Arduino
- Having the MP3 player connected normally, but with no speakers
A slightly less long shot, but costs a few bucks: have you tried a different MP3 player?