I'm running Ubuntu 9.04 and it plays MP3s fine.
You probably need to add the package ffmpeg to drag in a lot of decoders. Either use synaptic or, at a command prompt, enter:
sudo apt-get install ffmpeg
(it will then ask for your normal login password)
I had the opposite problem - the native Linux version won't open WMAs. I convert to MP3s using mplayer and lame (if you google for them, you should find a script to do it - can't remember offhand where it was). Quite possibly there is yet another package I could install to get WMA support.