I think one solution is having the prompts integrate with the sort of crowdsourcing algorithm that XPrivacy has (e.g., if >90% of users have granted the app permissions on the address book, then don't show the prompt.)
Another important feature is that the app should not know if the user has granted it the permissions it asked for. If the user doesn't want to, the system should just feed the app bogus data and let the user continue interacting with other parts of the app (as we see today, most apps don't really need the data they collect in order to work.)