This for me is part of a broader problem: Most users are that familiar with technology and effects of a specific permission are generally lost on them.
Apple Store's revision process is a PITA for devs, where you can be refused for strange and wierd reasons, but can catch a lot of the strange stuff.
Google's method of autoscanning for known problems is a great idea, but going further and releasing an app within either a preset of minimum permissions, and having a manual review if specific permissions are needed, for example:
Base: read/write in homedir, internet, accelerometer.
Navigation: Base + compass & gps.
Email : Base + mail access
Social : Base + address book
If for whatever reason the app requestes more privileges than these, it should then be submitted for manual approval, like if an app in the "Social" category wants SMS, mail and location priveleges, then it would have to be reviewed, and if the extra need cannot be explained by technical need, the app would not be validated (like Facebook: Why do you want privileges to read my SMS & Emails?), though this means that the revision process needs changing.
An easier automatic system would be, like on the iPhone, per app privileges. The phone checks the app against a valid category (default: Base) and all other privileges are deactivated. From there, it would be up to the app to request and explain why it needs whatever privileges for your contacts, GPS, SMS, Email, porn collection and unlubricated and unlimited access to your rectum at 3AM every morning. If you don't see why you need it, you don't go and activate it in the phone's "privilege center"... This means updating the OS and defining the base categories though, but at least this would have an effect on slowing down downloads from unknown third party sources sending premium rate SMS messages behind your back...
Finally, an app making outgoing calls or SMS should really generate a OS popup accept/refuse warning with the number called...