Help with creation, editing, or playback of sounds, images, or video. Amarok, audacious, mplayer, grip, cdparanoia and anything else that makes a sound or plays a video.
At least under Windows certain versions of VLC had severe issues with certain MKV files.
I found SMPlayer a better option for playing back HD MKVs under Linux than VLC. YMMV....
You could try another version of VLC or remux the MKV with the MKVMerge GUI.
May be this helps.