O Totem não reproduz arquivos .mkv corretamente, isso não é apenas um problema para você. Para mim, nem vai carregá-los, muito menos avançar. Aparentemente, o problema é diferente com a placa gráfica e / ou drivers que você usa.
Eu definitivamente recomendo usar o VLC (é livre como na liberdade), pode parecer feio e problemático no começo, mas você pode configurá-lo para parecer melhor e trabalhar ainda melhor que o totem.
Existem maneiras de consertá-lo, mas elas geralmente são complexas e não funcionam tão bem quanto usar o VLC pronto para uso. Essas correções não funcionam para a maioria dos usuários, então eu não sugeriria nem tentar.
Você também pode usar um player diferente, como o mplayer, se quiser, mas eu definitivamente recomendo o VLC dos três.