For the most part Rhythmbox works fine. However, there is one song in my library that it refuses to play, or add to any playlist. VLC will take it, and Audacity will as well, but Rhythmbox will just exit silently. Running with -d yields a similar output to the other non-broken MP3s. For what it's worth, I'm running Rhythmbox 2.96 with Ubuntu 12.04 Help?
Make a copy of your mp3, open it in Audacity and make a tiny inessential edit in it, perhaps cutting a little bit of time off the blank space at the end of it, and then save your mp3 at a slightly higher bitrate. Select File -> Export and from the Export File window select Options -> Specify MP3 Options -> and then change the Quality settings to a slightly higher bitrate. When you Export the mp3, redo every entry in the Edit Metadata window to make sure that the metadata tags for your exported mp3 have been entered correctly.