I really hate it when some apps require unnecessary permissions. Why would a game require access to my contacts or my personal photos and videos? Flicks me into the paranoid mode, especially since the news about Facebook and other major companies exporting your contact list and personal information to their servers.

I have seen an app (probably root-only) that can restrict specific permissions on applications. There are no promises if it will break the app or not, though.

Currently, removing an individual permission from an app will almost certainly cause an unhandled exception, since having that permission makes security exceptions for the corresponding API calls unexpected.

This could be changed without breaking existing apps.

Google could modify Android's app model just slightly, to enable apps to declare in their manifest that they support "a la carte" permissions and then enable users to select individual permissions. To work under this new permission model, apps would have to test for permissions, or handle security exceptions - small modifications.

I think this kind of change would be well worth it. For example, I prefer to trust the OS is preventing location tracking than that the app developer is being honest about turning it off in a setting.