I had the same problem on my new installed Linux-Desktop and solved it by editing the file /etc/mplayer/codecs.conf:
move the entry "audiocodec mad" before the entry "audiocodec mp3".