Are you viewing the video in the Youtube app on your iPhone or via Safari? It makes a
considerable difference as to how it's displayed. Via a browser (non-mobile) your viewers
will have the option to choose the "resolution" the file is sent at - down to 360p or
less, but much of what happens on Youtube is still based around Flash - and so the iPhone
uses its app.
My own uploads tend to be in H264 at 720p, and they seem to work well -
including the 3D ones (have a look at http://www.youtube.com/watch?v=xg_Y0S6jEtE
- but, again, it really
isn't targeted at mobiles). Youtube is still pretty much best used on a desktop rather
than mobile browser.