XenonMKV is a terrific program for converting videos in the MKV format to an MP4 that an Xbox 360 can play.
After upgrading my desktop PC to Windows 7 (64-bit), I found that the MP4 files I was outputting only worked if I changed the version of MP4Box.exe used to 0.4.5 (defaults to 0.4.6). After that I had no problems.