Mp4 en xbox

Es por el tipo de codec la Xbox es muy exquisita y si te sales del estandar no lo reproduce.

Puedes recodificar el video o reproducirlo via streaming

Me podrias explicar como hacer eso

Hay multitud de programas gratuitos para convertir avi a mp4 o viceversa, simplemente es ir probando cual te funciona.

Todo depende de si tienes PC, que versión de windows o linux(incluso mac)

Para streaming puedes hasta mirar en la página de microsoft
http://support.xbox.com/es-ES/apps/windows-media-center-on-xbox-360/windows-media-center-on-xbox-360-windows-7

Pero hay muchas posible soluciones según lo que busques en google:
"avi to mp4"
"streaming xbox"
etc...

Cuantos mas detalles des de lo que tienes mas ayuda podrá darsete.