Que lean el contenedor MKV, todos: Kaffeine, mplayer, VLC, bangarang, DragonPlayer... (imagino que estan todos para ubuntu, al menos estan en Mageia o Debian).
La cosa es que MKV solo es un contenedor, el (o los) stream de video que contenga puede estar codificado con diversos codecs (Xvid, h264, etc), y eso es lo que el programa tiene que soportar.
Quiza no tengas soporte para h264, ya que es un codec afectado por las ***** patentes de software, y estara en algun paquete restringido que has de instalar aparte. Sin duda tendras algo al respecto en el wiki de Ubuntu.
P.D.- Y si, como dice blackgem, di que error da, que decir "me da error" no ayuda a nadie.