I think 5MP-7MP is the sweet spot for a phone with limited storage. I have a Nikon D70 (6MP) dSLR which takes MUCH better photos than a good 12MP Canon IXUS and my Cybershot 7.2MP ultra-compact. I have no interest in upgrading the camera body either, despite the newer models taking much higher resolution pics.
Extra resolution is only worthwhile if you have a use for it all - if you're going to be doing lots of cropping, etc. Otherwise it really is nothing more than a waste of space and a way of adding more noise to the photo. Anyone actually leaving a 12MP phonecam at it's highest resolution setting - that seems pretty silly to me without a particular need for hyper-highres pics.
Extra resolution is only worthwhile if you have a big enough sensor for it all. Cramming 12 megapixels onto a sensor smaller than your thumbnail will get you horrible quality pictures with lots of grain and noise. (But the file sizes will be nice and big!) Take those same megapixels and spread them out across a sensor nearly the size of a single frame of 35mm film and the quality of the photo increases exponentially. That's not even taking into consideration the size/quality of the lens. (yeah, yeah, "objective")
Hell, with the size of these image sensors in phones (they are extremely tiny), even 3 megapixels is pushing the quality barrier. The backlit sensor in the iPhone 4 probably helps out significantly in this regard.