It took me ages to find info on creating Xbox 360 compatible videos on a linux box. In the end it turns out to be really easy using ffmpeg. Now, the problem with the 360 is that it requires videos to be in a very specific format, namely WMV video, WMA Audio and ASF container format. The following command will setup ffmpeg to use the source video settings for as much as possible, and sets the bitrate to 1.2 MBit/Sec.

ffmpeg -i "$INFILE" -vcodec wmv2 -acodec wmav2 -y -b 1200000 "$OUTFILE"