Handbrake can create videos that play on your iPhone. I've had pretty good success with everything I've tried. Here are the settings I use.

Output Settings:
File format: MP4
Codecs: AVC/H.2644 Video/ AAC Audio
Create chapter markers: Checked, if movie contains chapters

Video:
Framerate: 29.97fps
Encoder: x264 (h.264 iPod)
Bitrate: 768kb/s
Width: 480px
Height: (matching proportional to 480px)
2-pass encoding: Checked

Audio
Track 1 Mix: Stereo
Sample rate: 48khz
Bitrate: 128kb/s
Subtitles: none