Il me semble avoir pris la précaution du yum update hier, mais en répétant l'opération aujourd'hui j'ai un bon nombre de mises à jour. Possible que mon problème se résolve très simplement en fait. À suivre...
=> Bon, après mise à jour, l'installation automatique ne fonctionne toujours pas, mais j'ai résolu mon problème grâce à la doc.
Résolution du problème :
Pour les prochains : Il suffit d'installer le codec pour le "phonon-backend" que l'on veut utiliser.
Pour résumer :
su -
yum install phonon-backend-gstreamer gstreamer-plugins-ugly
Explications : Je voulais utiliser "phonon-backend-gstreamer" et seulement le mp3, j'ai installé le paquet "gstreamer-plugins-ugly"
Pour ceux qui veulent plus que le mp3, "yum update @sound-and-video" devrait fonctionner, toujours d'après la doc.
Lien vers la page de la doc d'Amarok :
http://amarok.kde.org/wiki/MP3_on_Fedora_Core
Problème résolu !