I coerced Fedora Core 5 Test 3 into playing MP3s (and maybe DVD). The patent issues make the licensing really truly ugly, and that trickles down into technical issues when a distro like Fedora plays indifferent to MP3 support. Don't tell anyone, but I have binary RPMs of what I did (mostly stolen, shamelessly) from Livna. Don't try these on FC4, they'll probably explode. The RPMs are here (and there's sources too). There's YUM and Poldek indices for those who want to figure out how to use them. I don't yet.
If you have SELinux enabled in enforcing mode, you may very well have to disable it -- there is a permission error, utterly unreported by things in the UI, that makes gstreamer ignore the mad plugin. Your mileage may vary.