With my version of rhythmbox (2.96) on 12.04, the .pls radio stream plays fine. Choose a stream from the site you are interested in; I chose this 128k mp3 stream from the site you mentioned and added it with Music > New Internet Radio station (as in the screenshot below).
Then on the sidebar (see screenshot below) click library > radio and the new station will probably be listed in the unknown genre slot. So then just double click the new station there.
It is also important to note that when you import a radio stream rhythmbox will sometimes assign a gender to it ('Space Electronica') and sometimes not. So, for example, this stream was to be found in 'Experimental Nujazz' when imported. If you can't find the station in the program's list, look through the genres or 'unknown' and double click a station if it doesn't play automatically.
If the stream doesn't play correctly, I should choose an alternative, as there are usually several available; for example, on this page the asx stream played the best.
In general, experiment with the different stream options available on the radio site you are interested in as rhythmbox has good support for .pls and .asx feeds, etc, when the necessary gstreamer plugins are installed.
If you can't get the .pls file working, you could just open it in a text editor and extract the url and then add that as a radio station in Rhythmbox, using the process I mentioned earlier in my answer.
You could also try installing the excellent rhythmbox-plugin-radio-browser from the ppa of one of our moderators, fossfreedom; do not install the version in the repositories as that version does not work with the current Rhythmbox.
sudo add-apt-repository ppa:fossfreedom/rhythmbox-plugins
sudo apt-get update
sudo apt-get install rhythmbox-plugin-radio-browser
You have to enable it by going to edit > plugins first.
More on the plugins available is explained here:
