You guys have it all wrong! The AppStore icons are treated EXACTLY like webclip icons. The icon is square, but then the iPhone adds the mask and shine to it. I *believe* you'll be able to change the icon just by replacing the Artwork in the "Get Info" window in iTunes. It makes sense... the App icons could be treated exactly like Artwork. Apple would be smart to do this so that people don't have to jailbreak to change an ugly icon.
Edit: I can't seem to paste anything over the default icon in iTunes so we may only be able to manually edit the package contents but, then again... the Code Signing may prevent the App from even launching if we modify it in any way. What a major bummer.