froyo (finally) has an automatic update feature, so most apps update on their own. i have noticed a few that say they require manual updating, but i didn't know if it was due to a download failure or if it was for a changed set of permissions. it does show you the full permission list again before updating manually.
How would you fix it? Ask the developer to simply say what the access will be used for? In an malicious app, they'd obviously just lie. Short of actually displaying what data an app is sending, I don't see an easy answer.
maybe show a list of domains it's allowed to resolve/contact? i guess that wouldn't make it any easier for most users to decipher though. i think a lot of free apps require network access just to download ads; maybe there is a better way (in the android api) of handling that to segment it away from full-blown network access?
maybe have a set of permissions common to each category? it's expected that a web browser app has access to do a lot of things, but if you have an app in a wallpaper category that requires those same set of permissions, it should be raising a red flag somewhere.
perhaps apple's app review process wasn't so crazy after all...