Just the other day I was trying to figure out how to get a video converted into the right format so I could chuck it onto my iPhone.
"If only Handbrake would read normal video files as well as DVDs" I was thinking.
Well turns out, it does with the latest version. Just point it at the video file (I'm trying it with an MP4), select the iPhone preset and away you go.

Works on Windoze and Linux too - check it out: http://handbrake.fr/