Here's what you need to do. First, get
MKVExtractGUI. Use that to extract the raw h.264 video and audio out of the file. Next, you need to convert the audio to 2ch lc aac if it isn't in that format already.
Then, get
Yamb. Open it and click on "Click on this item to create an MP4 file...". Place the video and audio into it. Go to the properties of the video and set the frame rate. After that, choose where to save it at and click next. Then hopefully it will work.
If it still won't play on the 360, then you will probably have to re-encode the video.