The stable versions of Rhythmbox are pretty unstable, and compiling the development releases is also kind of a bitch (you also need the development gstreamer). However, you should at least try to get the latest stable versions of rhythmbox and gstreamer.
Were you prompted to submit a bug report? Please do so. If you weren't prompted, you can use the GNOME bugzilla, as mentioned on .