What program are you using for this?
http://sourceforge.net/projects/mkvavi2mp4
It's for Windows... but great. Says it is for "iPad", but that's just compatibility with all Apple devices - including Apple TV.
Works wonders.
It also needs the Nero codec (no install needed for anything) here - http://www.nero.com/eng/downloads-nerodigital-nero-aac-codec.php.
I guess licensing issues, can't just bundle it all together.