How to fix Rhythmbox to play Mp3?
First of all remove it with:
$ sudo apt-get remove rhythmbox --purge
Update your sourcelist:
$ sudo apt-get update
Install o Rhythmbox again:
$ sudo apt-get install rhythmbox
UPDATE: Maybe you don't need to remove your Rhythmbox, just update the sourcelist and try to play. Then it will try to find the codecs. I think this because it solved my RMVB problem.