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 [1].
1.
http://www.rhythmbox.org/feedback.html
