I completely disagree with this. It might work as a business decision but it could cause problems in the future, especially if these early paying customers are vocal or previously bought your other apps. I think if a more popular/downloaded app did this (thrusting ads on paying customers) the backlash would be huge and it would severely damage the companies reputation. Just because you are a smaller business less likely to get press coverage for a bad decision doesn't give you a free pass to make it anyway.
As an app developer myself, I do care about my users. If a significant number of people will be negatively affected by a change I'm considering, I simply won't do it. It's just about where you draw the line. Is your stance that if even one person is affected in this way then it is unacceptable to make the business decision to shift to ads?
I've just started using Parse for analytics, error/crash reports and promo codes. Seems to be working well although I haven't started analysing the usage data systematically yet but I have found a number of errors I wasn't aware of from the error reports.
Http://iTunes.com/apps/fastlists
Promo codes have gone out to a couple of bug reporters (who weren't expecting them) and friends and family. When I've stabilised all the bugs and added a sync system I'll send them out to reviewers too.
New version in review should fix most of the errors (only one of which I have received user feedback about despite having a report a bug option in the settings and promising to provide freebie upgrade for users that report bugs).
I recently added in-app purchases and ads (iPhone only for ads so far). I had one bad review for offering 'Privacy' as an in-app purchase that would disable the anonymous logging and I've renamed that item. Otherwise no complaints. I did grandfather existing (free) users into unlimited items and readable email as I didn't want to remove existing features from people while imposing (high) limits on new customers that require in-app purchase to lift or remove. If the existing user installs the app on a new device they will have to buy (if they complain nicely they might get a promocode).
Also, iCloud's NSUbiquitousKeyValueStore gives us NSUserDefault-like data storage that syncs across the user's iCloud account (iOS 5 and up required). This makes the firstLaunchData approximation very near to perfect.
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.