Usa el mencoder, es rapido y simple. Sirve en cualquier OS Linux, Windows, OSX..etc
Abre una terminal, y escribe
mencoder video.mkv -oac mp3lame -ovc copy -o salida.avi
Lo que hace ese comando, es convertir el mkv a un avi, sin recodificar el video, y recomprimiendo el audio a mp3
Asi no perdes calidad, pero tenes un avi compatible
En caso que quieras recodificar video, por ejemplo a xvid, el comando seria mas o menos asi
mencoder video.mkv -oac mp3lame -ovc xvid -xvidencopts pass=2:bitrate=800 -o salida.avi
Espero te sirva