Entonces tu problema NO es con los codecs, sino con tu configuración de mplayer.
Prueba alguno de estos comandos:
Código:
mplayer -vo x11 /ruta/a/un/video.avi
mplayer -vo xv /ruta/a/un/video.avi
mplayer -vo help
Este último te entregará una lista de todos los drivers de video soportados por tu versión de mplayer. Los más usados son x11 y xv (los que te sugerí en los primeros dos comandos).
PD: "restart playback" ~= "reiniciar la reproducción".