Confirming this was a long standing bug with Rhythmbox I set out looking for a better player. So yesterday evening I tried out XMMS which worked very satisfactorily. After spending a while on XMMS i started missing the most important functions of chaning the next and previous tracks. Evidently the shortcut buttons on my Lenovo 3000 N100 did not work, which were able to control Rhythmbox properly. Obviously shuffling was more important than control so XMMS had to remain, but some googling, and i had the following packages that allowed me to put a little bit of control on the taskbar
yum install xmms
yum install gnome-applet-music
yum install pyxmms
Once installed, you just need to add the applet to the taskbar

I don't usually like the Wine-ish look that XMMS has, so I also tried out gXMMS2 but after it would not even import my collection I let it rest in the repo server itself.