As I recall, iPods and iPhones will only play certain resolution MP4 and H.264 videos. They have to be a certain constrained resolution.
According to the tech specs for the iPhone 4, your movie has to fall under these specific parameters: Video formats supported: H.264 video up to 720p, 30 frames per second, Main Profile level 3.1 with AAC-LC audio up to 160 Kbps, 48kHz, stereo audio in .m4v, .mp4, and .mov file formats; MPEG-4 video, up to 2.5 Mbps, 640 by 480 pixels, 30 frames per second, Simple Profile with AAC-LC audio up to 160 Kbps per channel, 48kHz, stereo audio in .m4v, .mp4, and .mov file formats; Motion JPEG (M-JPEG) up to 35 Mbps, 1280 by 720 pixels, 30 frames per second, audio in ulaw, PCM stereo audio in .avi file format
I found this information here:
http://www.apple.com/iphone/specs.html
Hope this helps!
I am guessing your audio might not be compressed correctly, but according to the tech specs it CAN play 720p H.264