I first tried this in January, 2013 using Fedora 17, x86_64, and obtained a popup telling me I needed a plugin. The popup offered to search (which was useless as it turned out). I next tried to yum install gstreamer*, which also did not get me going.
What did work was to download the Fluendo plugin. What you do is to register at this site (which is in Spain), then purchase the plugin (which is free). I obtained it as an RPM for x86_64. It installs in seconds and you are in business.
All this is due, apparently, due to some legal issues with MP3 algorithms in certain area (apparently the USA is one of those areas).
Adventures in Computing / [email protected]