iPhone "cannot play" .mp4 H.264 video file
The problem was partially to do with encoding but more to do with the dimensions.
I found out that if your .mp4 file is larger in dimension than 640*360 then the iPhone (iPad, iPod) won't even give the user the option to attempt to play it. They just get the X'd out play button icon.
Also, these devices only support .mp4's that are encoded with the baseline H.264 profile, or they can't be played.
Also, there's a bitrate limit of 1.5Mb for the iPhone, but it's suggested to keep the bitrate below 900kb.
If quality is less of a concern than size then you can use m4v's of larger dimensions but I believe the bitrate rules still apply.
I encountered a similar issue and my guess was encoding. I had tried the "iPhone" preset with Adobe Premiere CS4 (Adobe Media Encoder) with no luck.
Running it through ffmpeg with the following did the trick:
ffmpeg -i INPUT -s 320x240 -r 30000/1001 -b 200k -bt 240k -vcodec libx264 -coder 0 -bf 0 -refs 1 -flags2 -wpred-dct8x8 -level 30 -maxrate 10M -bufsize 10M -acodec libfaac -ac 2 -ar 48000 -ab 192k OUTPUT.mp4
I found the above (and many other configurations) here: http://rodrigopolo.com/ffmpeg/cheats.html (I corrected a few typos in their "iPod-iPhone 640 width, without presset" [sic].)
Other searching around will probably yield more information about the encoding requirements (h.264 baseline 3.0) and size requirements for the movie to play on the iPhone.
The official Apple reference on the subject: http://developer.apple.com/library/safari/#documentation/AppleApplications/Reference/SafariWebContent/CreatingVideoforSafarioniPhone/CreatingVideoforSafarioniPhone.html