Xbox 360 multimedia capabilities are very good, with streaming functions available not only for Windows systems (see here for streaming movies using Ubuntu).
There is a caveat though, the lack of subtitles functionality for movies, and the only way to use them is to hard-sub (encoding the movie again applying subtitles on it).
Mencoder is available in almost every Linux distribution, for install on Ubuntu just type:
sudo apt-get install mencoder
I encode each movie in Xvid format (which Xbox is capable of play), with this command:
mencoder mymovie.avi -ovc xvid -oac mp3lame -xvidencopts fixed_quant=1 -sub mymovie.srt -o mymovie-encoded.avi
where obviously mymovie.avi is the original movie without subtitles, mymovie.srt is the subtitles file and mymovie-encoded.avi is the resultant output file.
The output file will be larger than the original one because I used the fixed_quant=1 option, that outputs larger files but with best quality (you can use 2 or 3 but the quality downgrades).
Encoding may be very slow on older systems, but once finished it can played as any other media…enjoy!