I know some people have been successful on here with converting their MKV contained videos to compatible formats (i.e. mp4 container), however I can't be bothered to spend hours re-encoding all my existing videos, so went on the look out for an easier solution and found this 
The above is a direct quote from another forum; there seems to be some talk of scene related stuff there so I won't paste a direct link to the forum, but credit goes to J^^ for originally posting this up there

J^^ said:Here is a quick and easy way to convert an MKV to an MP4 for the 360...
1. Using MKVmerge demux the video and audio from your MKV file.
2. Using whichever software you choose, convert the audio to MP4 (remember it has to be 2 channel AAC LC). This can be done with a number of different programs.... choose whichever one you are most familiar with (ie. meGUI, foobar2000 (with the proper plugins), etc.)
3. Using h264info change the level of the video (the .h264 file) to 4.1 (This will not re-encode the video so it will only take a few minutes to re-write). Make sure that the output filename is different than the input or it will fail.
4. Using MP4Box or YAMB (to avoid command lines) remux the video and audio.
That's it! You are now ready to play the new file without suffering though a lengthy re-encoding process!
Remember that this only works if your video bitrate is already below the max of 10 Mbps (with resolutions of 1920x1080 and a framerate of 30fps).
Hope this saves some of you lots of time!
The above is a direct quote from another forum; there seems to be some talk of scene related stuff there so I won't paste a direct link to the forum, but credit goes to J^^ for originally posting this up there
