OK, wait a minute...
There is no *legal* way to listen to MP3s in Linux? There is no free player?
As a post script, I wanted to clarify my last post by pointing out that there isn't so much a legal limitation on listening or decoding mp3's on Linux as there is a lack of software which can be legally redistributed by Fedora / Red Hat for that task. You can download GPL'd MP3 players from the authors of that software, but you will not have a valid license to restribute that software if you're in a location affected by Thompson's patents.