I had some joy using custom firmware and the ffmpeg package to quickly convert some mkvs to mp4s on the box.
Like af123 said, mkvs are just a container and it does depend what's inside them but confusingly the Humax will sometimes play the same combination of audio/video stream contained in an mp4 that it refused when in an mkv.
Changing the container is a much quicker process than re-encoding a file. The humax can change a 1hr mkv into a mp4 in about 5min and I assume on a modern PC it would be almost instantaneous.
What happens when you start to play one of your mkvs? It's the ones that start to play until the sound should cut in that I had success with.