Both the iPhone and Google Android phones seem to have limited codec support when it comes to video. Both support MP4, so I did a bit of searching on the internet to find out how to convert to a suitable format using MPlayer's MEncoder.
Video cannot have a high compression rate, and the video size generally needs to be scaled down to 480:352. The video codec used here is x264 with a bitrate of 512.
I'm sure there are multiple ways of doing it, however the following combination works for me:
mencoder <inputfile> -o <outputfile>.mp4 \
-vf dsize=480:352:2,scale=-8:-8,harddup \
-oac faac -faacopts mpeg=4:object=2:raw:br=128 \
-of lavf -lavfopts format=mp4 -ovc x264 -sws 9 \
-x264encopts nocabac:level_idc=30:bframes=0:bitrate=512:threads=auto:turbo=1:global_header:threads=auto:subq=5:frameref=6:partitions=all:trellis=1:chroma_me:me=umh
Let me know if it works for you, and which phone you are using!