Eu também estou com alguns problemas com o Rhythmbox.
Não consigo acessar a webradio da meurock.com, somente as que já estão na lista. Já instalei o GsStreamer (acho que o nome é esse) e outros tantos codecs, a rádio toca pelo chrome e pelo Reprodutor de filmes, mas no Rhythmbox não toca nem a pau.
Eu cliquei em adicionar nova estação e digitei o endereço da rádio
http://www.meurock.com/webrocxk.asx assim como fiz nos outros players.
No ubuntu 10.4 pegava numa boa.