Check out Parse. They aren't an analytics provider. They provide a generic backend API that you can use with your apps to store and fetch whatever data you desire. For the number of user's you're probably working with, and the number of events you'll want to log, you will most likely stay under their 1,000,000 free requests per month (and if you don't, the $200/mo expense will probably be acceptable to you given your app's monthly revenue).
>If Apple provided a reliable way to determine who had already paid, I would have just automatically disabled ads for people who had paid.
Two things here: first, you should have only shown the adds to new users. That would have been the safest play to avoid backlash from existing users. Second, this is why it's a great idea to track "firstLaunchDate" in the NSUserDefaults in 1.0 versions of your future apps. With that single piece of information you would have been able to target exactly who sees the adds and who doesn't.
Edit: I wanted to add I think you might be making a mistake backing down at this point. It seems that all of the problems you mention in this post relate to some small (yet vocal) percentage of your existing users being upset with the recent changes. That's a temporary problem, and probably not that big of a deal at this point since you've already absorbed the majority of the backlash you're going to get. If you think the changes you made in your latest version are the right direction for your product in the long run, then I'd stay the course.