Hello, I had the same problem (I installed rhythmbox without gnome), and installing python-gst didn't fix the errors I got with the Jamendo and Magnatune plugins.
I fixed it by installing libgnomevfs2-extra It would be nice to fix this, it took me a lot of time to figure it out. Thank you for your time. Rol--and
