Have you tried just going to gmail.com ? Their iPhone interface is pretty darn good. Many people like it better than the mail app (so lifehacker claims). That being said, I use lots of labels (though few multi-label items) and I have no trouble with the iPhone mail app...