Have you encoded your video using correct settings? Video cedec should be H.264 and resolution below 480x352 I think. I recommend you to use HandBrake to do this, you can download it from here
HandBrake elect the iPhone profile and it should work fine. Good luck.