Using Ubuntu 9.04 the new Amarok 2 stopped working. Some tries showed that Internet Radio is still fully functional. Some search offers many tricks and tweaks but none of them helped.
At the end it seems to help to install another phonon backend. Some posts indicate that you have to install either gstreamer or xine backends.
sudo apt-get install phonon-backend-xine
sudo apt-get install phonon-backend-gstreamer
Another approach may just be, that xine is missing some mpeg playback features.