Como alguns releases do Ubuntu não têm o ffmpeg (explicação detalhada em inglês [pdf]), você terá que usar o avconv (pacote libav-tools, do projeto Libav) que funciona basicamente com os mesmos parâmetros.
De MKV para MP4:
$ avconv -i input.mkv -c:v copy -c:a copy -sn output.mp4
De MP4 para MKV:
$ avconv -i input.mp4 -c:v copy -c:a copy -sn output.mkv
Fontes:
- http://askubuntu.com/questions/50433/how-to-convert-mkv-file-into-mp4-file-losslessly#comment307558_195346
- http://blog.pkh.me/p/13-the-ffmpeg-libav-situation.html [pdf]
- http://www.webupd8.org/2014/11/ffmpeg-returns-to-official-ubuntu.html
- https://wiki.debian.org/Debate/libav-provider/ffmpeg [pdf]
- http://askubuntu.com/questions/432542/is-ffmpeg-missing-from-the-official-repositories-in-14-04