Xbox 360 plays none of my videos

I am able to see all of my movies on the Xbox 360. When I select to play them however, I get an unsupported format error.
Here is the ffmpeg -i output of one such file.
ffmpeg version git-2013-01-10-f023003 Copyright (c) 2000-2013 the FFmpeg developers
built on Jan 10 2013 01:39:13 with gcc 4.4.3 (Ubuntu 4.4.3-4ubuntu5.1)
configuration: --enable-gpl --enable-libfaac --enable-libmp3lame --enable-libopencore-amrnb --enable-libopencore-amrwb --enable-libtheora --enable-libvorbis --enable-libvpx --enable-libx264 --enable-nonfree --enable-version3 --enable-x11grab
libavutil 52. 13.100 / 52. 13.100
libavcodec 54. 86.100 / 54. 86.100
libavformat 54. 59.107 / 54. 59.107
libavdevice 54. 3.102 / 54. 3.102
libavfilter 3. 32.100 / 3. 32.100
libswscale 2. 1.103 / 2. 1.103
libswresample 0. 17.102 / 0. 17.102
libpostproc 52. 2.100 / 52. 2.100
home/tim/Downloads/Dredd/Dredd.2012.1080p.BluRay.x264.YIFY.mp4: No such file or directory
tim@tim:~$ ffmpeg -i Downloads/Dredd/Dredd.2012.1080p.BluRay.x264.YIFY.mp4
ffmpeg version git-2013-01-10-f023003 Copyright (c) 2000-2013 the FFmpeg developers
built on Jan 10 2013 01:39:13 with gcc 4.4.3 (Ubuntu 4.4.3-4ubuntu5.1)
configuration: --enable-gpl --enable-libfaac --enable-libmp3lame --enable-libopencore-amrnb --enable-libopencore-amrwb --enable-libtheora --enable-libvorbis --enable-libvpx --enable-libx264 --enable-nonfree --enable-version3 --enable-x11grab
libavutil 52. 13.100 / 52. 13.100
libavcodec 54. 86.100 / 54. 86.100
libavformat 54. 59.107 / 54. 59.107
libavdevice 54. 3.102 / 54. 3.102
libavfilter 3. 32.100 / 3. 32.100
libswscale 2. 1.103 / 2. 1.103
libswresample 0. 17.102 / 0. 17.102
libpostproc 52. 2.100 / 52. 2.100
Input #0, mov,mp4,m4a,3gp,3g2,mj2, from 'Downloads/Dredd/Dredd.2012.1080p.BluRay.x264.YIFY.mp4':
Metadata:
major_brand : isom
minor_version : 1
compatible_brands: isomavc1
creation_time : 2012-12-25 15:06:30
Duration: 01:35:51.79, start: 0.000000, bitrate: 2241 kb/s
Stream #0:0(und): Video: h264 (High) (avc1 / 0x31637661), yuv420p, 1920x800 [SAR 1:1 DAR 12:5], 2141 kb/s, 23.98 fps, 23.98 tbr, 96k tbn, 47.95 tbc
Metadata:
creation_time : 2012-12-25 15:06:30
Stream #0:1(eng): Audio: aac (mp4a / 0x6134706D), 48000 Hz, stereo, fltp, 95 kb/s
Metadata:
creation_time : 2012-12-25 15:06:42
handler_name : GPAC ISO Audio Handler
What can I do to correct this?
Thanks!
Here is the ffmpeg -i output of one such file.
ffmpeg version git-2013-01-10-f023003 Copyright (c) 2000-2013 the FFmpeg developers
built on Jan 10 2013 01:39:13 with gcc 4.4.3 (Ubuntu 4.4.3-4ubuntu5.1)
configuration: --enable-gpl --enable-libfaac --enable-libmp3lame --enable-libopencore-amrnb --enable-libopencore-amrwb --enable-libtheora --enable-libvorbis --enable-libvpx --enable-libx264 --enable-nonfree --enable-version3 --enable-x11grab
libavutil 52. 13.100 / 52. 13.100
libavcodec 54. 86.100 / 54. 86.100
libavformat 54. 59.107 / 54. 59.107
libavdevice 54. 3.102 / 54. 3.102
libavfilter 3. 32.100 / 3. 32.100
libswscale 2. 1.103 / 2. 1.103
libswresample 0. 17.102 / 0. 17.102
libpostproc 52. 2.100 / 52. 2.100
home/tim/Downloads/Dredd/Dredd.2012.1080p.BluRay.x264.YIFY.mp4: No such file or directory
tim@tim:~$ ffmpeg -i Downloads/Dredd/Dredd.2012.1080p.BluRay.x264.YIFY.mp4
ffmpeg version git-2013-01-10-f023003 Copyright (c) 2000-2013 the FFmpeg developers
built on Jan 10 2013 01:39:13 with gcc 4.4.3 (Ubuntu 4.4.3-4ubuntu5.1)
configuration: --enable-gpl --enable-libfaac --enable-libmp3lame --enable-libopencore-amrnb --enable-libopencore-amrwb --enable-libtheora --enable-libvorbis --enable-libvpx --enable-libx264 --enable-nonfree --enable-version3 --enable-x11grab
libavutil 52. 13.100 / 52. 13.100
libavcodec 54. 86.100 / 54. 86.100
libavformat 54. 59.107 / 54. 59.107
libavdevice 54. 3.102 / 54. 3.102
libavfilter 3. 32.100 / 3. 32.100
libswscale 2. 1.103 / 2. 1.103
libswresample 0. 17.102 / 0. 17.102
libpostproc 52. 2.100 / 52. 2.100
Input #0, mov,mp4,m4a,3gp,3g2,mj2, from 'Downloads/Dredd/Dredd.2012.1080p.BluRay.x264.YIFY.mp4':
Metadata:
major_brand : isom
minor_version : 1
compatible_brands: isomavc1
creation_time : 2012-12-25 15:06:30
Duration: 01:35:51.79, start: 0.000000, bitrate: 2241 kb/s
Stream #0:0(und): Video: h264 (High) (avc1 / 0x31637661), yuv420p, 1920x800 [SAR 1:1 DAR 12:5], 2141 kb/s, 23.98 fps, 23.98 tbr, 96k tbn, 47.95 tbc
Metadata:
creation_time : 2012-12-25 15:06:30
Stream #0:1(eng): Audio: aac (mp4a / 0x6134706D), 48000 Hz, stereo, fltp, 95 kb/s
Metadata:
creation_time : 2012-12-25 15:06:42
handler_name : GPAC ISO Audio Handler
What can I do to correct this?
Thanks!