Ubuntu 9.04 here, same problem. Installing phonon-backend-xine and removing phonon-backend-gstreamer solved it for me!
Here libxine1-ffmpeg was already installed.
Ubuntu 9.04 here, same problem. backend- gstreamer solved it for me!
Installing phonon-backend-xine and removing phonon-
Here libxine1-ffmpeg was already installed.