Tive um problema semelhante: ao rodar o mplayer pelo terminal aparecia mensagem de erro e demorava muito pra abrir, sem falar quando não abria. Quando apenas reinstalei o mplayer não resolveu. Então deletei o diretório oculto .mplayer e removi o mplayer junto com alguns outros pacotes que vieram junto e instalei de novo. Aí voltou a funcionar.
É... Eu fui no Sinaptic, fiz remoção completa, deletei o .Mplayer, reinstalei pelo terminal e.. resolveu! Agora, para realmente funcionar é necessário ter também o W32codecs e o ffmpg. Outra coisa (recomendada, não obrigatória) é rodá-lo em OpenGL. Se você tiver uma GeForce, é moleza! Para rodar vídeos em MKV, MP4, MPG e quiçá AVI use o comando:
gmplayer -vo gl
E para RMVB deve ser:
gmplayer -vc rv40
Assim, eu só dependo do Totem para FLV.