Commence par tout mettre à jour :
sudo aptitude update
sudo aptitude upgrade
Pour amarok il faut installer libxine1-ffmpeg (mp3) en plus des paquets spécifiques à amarok (amarok amarok-engines amarok-xine) :
sudo aptitude install libxine1-ffmpeg amarok amarok-engines amarok-xine
Du coup xine devrait marcher par la même occasion. Pour rhythmbox cf ce que j'ai dit dans <2>, vérifie que niveau plugin tout est installé. Pour faire marcher les players qui ne sont utilisent d'autre decodeur que xine (notamment xmms, rhytmox, mplayer doivent en faire partie) vérifie que tu as installé les plugins gstreamer, vorbis (ogg), musepack (mpc) :
sudo aptitude install gstreamer0.10-plugins-base gstreamer0.10-x gstreamer0.8-plugin-apps gstreamer0.8-tools vorbis-tools xmms-musepack
En cas de soucis merci de me reporter les messages d'erreur d'aptitude.
Bonne chance