I used to use 720 unless I wanted really good quality for something. Because of the extra size of the files. Now I have all my music I Amazon's cloud and have 26gb available for my videos so I use 1080 all the time.
Not sure one can tell the difference between 720 and 1080 on a screen as small as a phone. I'd be amazed if a person could tell the difference. The only reason I'd use 1080 is because I am too lazy to re-encode to 720.
I use both, mostly 1080p when I first got the Galaxy Nexus but now I use 720p more often, especially action videos like my son's basketball games. With the higher frame rate of 30fps in 720p I find they are less choppy than the 1080p at 24fps.
I don't know how you missed another recently created similar thread (mine) when you typed this thread title, but it has a link to a great video review on this subject. Basically, 720 gives a smoother video because of the 30 frames vs 1080's 24.