Estava com esse problema e graças a milhões de tutorias na internet consegui resolver. Essa dica tem como objetivo poupar tempo.

Primeiro instalaremos o RPM Fusion:

su -c 'yum localinstall --nogpgcheck http://download1.rpmfusion.org/free/fedora/rpmfusion-free-release-stable.noarch.rpm http://download1.rpmfusion.org/nonfree/fedora/rpmfusion-nonfree-release-stable.noarch.rpm'

E instalaremos os codecs:

Para GNOME:

su -c 'yum install gstreamer{1,}-{ffmpeg,libav,plugins-{good,ugly,bad{,-free,-nonfree}}} ffmpeg'

Para KDE:

su -c 'yum install xine-lib* k3b-extras-freeworld'

E para streaming no Rhythmbox:

su -c 'yum install gstreamer{1,}-{plugin-crystalhd,ffmpeg,plugins-{good,ugly,bad{,-free,-nonfree,-freeworld,-extras}{-extras}}} ffmpeg libmpg123 lame-libs'

E caso não haja nenhum player:

su -c 'yum install vlc'

E se não funcionar recomendo este codecs:

su -c 'yum install audacious-plugins-freeworld-mp3 xmms-mp3'

Espero ter ajudado, e que ao fim consiga reproduzir seus áudios e vídeos.