Tu choppes le package "all" contenant tout les codecs initialement prévu pour mplayer, dont voici le lien:
http://www2.mplayerhq.hu/MPlayer/releases/codecs/all-20050412.tar.bz2

Tu l'enregistres où tu veux et tu le décompresses --> extraire ici.
Là tu te retrouves avec avec un fichier all...
Maintenant tu vas ouvrir nautilus en mode super-utilisateur (ATTENTION ne touche qu'au fichier que je t'indique sous risque de mettre ton installation en péril en manipulant des dossiers que tu ne devrais pas).

En console:
sudo nautilus
Tu copies l'intégralité des codecs présents dans ton fichier "all...."
Maintenant tu te rends dans /usr/lib/win32
Et là tu colles l'intégralité des codecs, on va te dire que tel codec est déjà présent et tu fais "remplacer tout"
C'est tout pour nautilus et tu peux le fermer.
On retourne à synaptic et là tu reinstalle le lecteur de ton choix, et là avec ça si ça marche pas...