El problema es el codec de mp3 de GStreamer, banshee usa GStreamer y el codec de mp3 no viene incluido en Fedora.
Para instalar el codec usaremos el repositorio de RPM Fusion, los pasos a seguir son los siguientes:
su -c ‘rpm -Uvh http://download1.rpmfusion.org/free/fedora/rpmfusion-free-release-stable.noarch.rpm http://download1.rpmfusion.org/nonfree/fedora/rpmfusion-nonfree-release-stable.noarch.rpm’
su -c ‘yum install gstreamer-plugins-ugly -y’
Tras esto ya podremos escuchar nuestros ficheros de mp3 en banshee