Just to be sure: do the MP3 files play in Totem (or other player that uses GStreamer)? If so, the codecs are installed properly.
Have you tried deleting the rhythmbox directory in ~/.local/share to delete its database and try to build it again now that the codecs are installed?