Então para você poder adicionar a legenda ao filme, e ainda mantê-lo em MKV, você precisa de um programa chamado mkvmerge. Aqui vou dar a dica de como instalar no Ubuntu, ou Ubuntu-like, como é o meu caso, mas no site original tem as instruções para mais sistemas.
Primeiramente você precisa adicionar a chave do repositório pelo seguinte comando:
wget -O - http://www.bunkus.org/gpg-pub-moritzbunkus.txt | sudo apt-key add -
Depois adicione a fonte de acordo com a sua versão de Ubuntu.
11.10: deb http://www.bunkus.org/ubuntu/oneiric/ ./
12.04: deb http://www.bunkus.org/ubuntu/precise/ ./
10.04: deb http://www.bunkus.org/ubuntu/lucid/ ./
10.10: deb http://www.bunkus.org/ubuntu/maverick/ ./
11.04: deb http://www.bunkus.org/ubuntu/natty/ ./
Não se esqueça de atualizar os repositórios:
sudo apt-get update
E então pode instalar o programa.
sudo apt-get install mkvtoolnix mkvtoolnix-gui
Be happy!