Here are the informal results via quick tabulation of a poll on how people start their iPhone User Interface designs. I ask this question on iPhone Developers Group on LinkedIn and Twitter. Roughly 32 folks replied. Please note some people responded with multiple tools. Thanks for all the great response.

Paper:22   IB:10   Photoshop:6  Omnigraffle: 3  Balsamiq:3 

White Board:2

Single mentions on iPlotz, http://iphonemockup.lkmc.ch, Keynote, Visio, OpenOffice Impress, IA WireFrame, and Flash.

Paper is your winner by a landslide. The Trees never stood a chance. Not surprising IB coming in second.  I like Paper to start also. Stay tuned I might have something interesting to offer along those lines.