Eu tive exatamente o mesmo problema. Esta resposta aqui resolveu o problema.
Eu segui o último, ou seja,
Instale o vlc com sudo apt-get install vlc
e, em seguida, instale os plugins necessários para reproduzir arquivos * .mkv por sudo apt-get install vlc-plugin-libde265
Note que, se a instalação do plugin lhe deu um erro não encontrado, você precisará adicioná-lo ao repo primeiro
sudo apt-add-repository ppa:strukturag/libde265
sudo apt-get update
Agora tente abrir o arquivo em vlc.