O problema relatado se refere a falta de codecs apropriados, o que pode ser resolvido com a instalação do repositório medibuntu e de codecs non-free, restrict-extra, lame, ffmpeg...
Depois de instalar os codecs os vídeos funcionam normalmente no Totem (aplicativo padrão do ubuntu). O Kmplayer é uma interface KDE do mplayer, assim como o Gnome-mplayer. Por ser KDE, no ubuntu padrão, o desempenho acaba sendo reduzido, pois o sistema precisa carregar bibliotecas KDE antes de rodar o aplicativo.
Até o 11.10 eu diria que o Gnome-mplayer é a melhor opção (só usava ele), mas, no 12.04 tem um bug dele com o unity, que faz com que funcione mal, as vezes sem imagem.