Found a (non-free) solution. Quicktime Pro and Perian FTW. With QT & Perian 1.x, I can open the .mkv file in Quicktime. Then I export as MPEG-4 (H.264) using "passthrough" (i.e. it doesn't reencode). Should work beautifully. My demo file crashes the AppleTV, though. ... I think there was something wrong with the MKV-file, though, since it also gives an error message on VLC. I'll try with another to verify.