Geralmente é o próprio arquivo que é o problema, não o Totem ou o VLC. Certifique-se de ter codificado o arquivo corretamente.
O FFMpeg é ótimo para codificação; codificar seu arquivo para um formato diferente pode resolver o problema.
ffmpeg -i Test.mp4 -sameq -r 24 Test.mov
é geralmente o comando que eu uso.
Aqui está uma longa lista de opções para codificar arquivos de vídeo / áudio.