One thing that Google did well when building their platform is integrating permissions into the install process. Like Facebook's OAuth permissions, users understand how to interact with this. Don't care about ads tracking you but want more features that rely on tracking? [x] Allow tracking.

If Apple took a page from their book, they wouldn't need to take such drastic action, but instead let developers decide if users want the features that require those permissions.