Rhythmbox uses the GStreamer plugin system for media decoding. The plugins that are installed will determine which formats you will be able to play.
By default Fedora 23 includes the necessary plugins for decoding free formats. To search for the packages that support the media you want to play visit GStreamer.
A quick search on our Fedora 23 system reveals which plugins are pre-installed
rpm -qa | grep gstreamer libnice-gstreamer1-0.1.13-2.fc23.x86_64 PackageKit-gstreamer-plugin-1.0.10-2.fc23.x86_64 gstreamer1-plugins-bad-free-1.6.1-2.fc23.x86_64 gstreamer1-1.6.1-1.fc23.x86_64 gstreamer1-plugins-base-1.6.1-1.fc23.x86_64 gstreamer1-plugins-good-1.6.1-1.fc23.x86_64
None of these provide MP3 playback. To enable this plugin you must first add the RPM Fusion repository.
To enable access to both the free and the nonfree repository use the one liner below
su -c 'dnf install http://download1.rpmfusion.org/free/fedora/rpmfusion-free-release-$(rpm -E %fedora).noarch.rpm http://download1.rpmfusion.org/nonfree/fedora/rpmfusion-nonfree-release-$(rpm -E %fedora).noarch.rpm'
On the GStreamer site we can see that in order to play MP3s we need the plug-in named gst-plugins-ugly. In Fedora this package is named gstreamer1-plugins-ugly.
sudo dnf install gstreamer1-plugins-ugly
For our convenience DNF automatically pulls in all the required dependencies.
a52dec, lame-libs, libmad, libmpeg2, opencore-amr, twolame-libs, x264-libs
Show the GStreamer packages after install
rpm -qa | grep gstreamer libnice-gstreamer1-0.1.13-2.fc23.x86_64 PackageKit-gstreamer-plugin-1.0.10-2.fc23.x86_64 gstreamer1-plugins-bad-free-1.6.1-2.fc23.x86_64 gstreamer1-1.6.1-1.fc23.x86_64 gstreamer1-plugins-base-1.6.1-1.fc23.x86_64 gstreamer1-plugins-good-1.6.1-1.fc23.x86_64 gstreamer1-plugins-ugly-1.6.1-1.fc23.x86_64
If for some reason you still receive an error when trying to play your media try deleting the following file
Rhythmbox automatically recreates this file the next time a user attempts to play some media. Rhythmbox adds an entry type = ignore which appears to blacklist media when a codec is not available for playback. Deleting the file resolves the issue.
One my preferred audio players. This one liner installs the program along with the plugin for MP3 playback.
sudo dnf install audacious audacious-plugins-freeworld