Since I did all the research on this yesterday to get it working, I figured I’d share it with the world in case someone else is having problems with it too! These instructions assume Ubuntu, but should work on pretty much any Linux system with minor modifications.

1) You must have a GStreamer player installed. Totem (the defaul GNOME movie player/media player) is what I used because it was already installed.
2) Install gstreamer0.10-plugins-bad with Synaptic
3) Go to MPlayer and download the binary codecs for Linux. Unpack the file into either the /usr/lib/win32/ directory or the /usr/lib/codecs directory (depending on your system, I put it in both to be safe).
5) Install gstreamer0.10-pitfdll with Synaptic (if available) or get it from a mirror.
4) Install gstreamer0.10-plugins-ugly with Synaptic

That should be it! You should now be able to listen to Internet radio stations in the Windows Media format.