This definitely comes under the Bin Of Knowledge heading. In a google I found many people with this problem, but no mention of my particular solution, so maybe this will help at least a handful of folks out there.
I have an Xbox360 through which I stream content from a LaCie EDMini NAS disk, which serves up files via TwonkyMedia. To be honest, it's usually music, but last night I felt the urge to do some learning and so decided to watch some episodes of Meet The GIMP (highly recommended by the way, if you enjoy listening to earnest Germans discuss the finer details of sRGB colour space - and who doesn't?). These come as .mp4 files, but the Xbox mysteriously didn't seem to recognise them, even though they're supposed to be supported. That was until I downloaded one episode that had an .MP4 extension (note the capitalisation), which did appear.
This led to one of those "tch, I know this isn't going to work, but I'll try it on the crazy off-chance" moments, where I renamed the files to end with the .MP4 extension instead of .mp4. And voila, there they were on the Xbox.
I'm not sure where the problem lies on this one, whether the Xbox or Twonky, but don't say I don't give you things.