gstreamer0.10-ffmpeg wasn't installed on my system and I had the same problem. However installing gstreamer0.10-plugins-ugly got rid of the issue.
(rhythmbox 0.13.1-0ubuntu5, Ubuntu 10.10 x86)
gstreamer0. 10-ffmpeg wasn't installed on my system and I had the same problem. However installing gstreamer0. 10-plugins- ugly got rid of the issue.
(rhythmbox 0.13.1-0ubuntu5, Ubuntu 10.10 x86)