The nature of email clients, especially ones that integrate with cloud-hosted spam and filtering services, is that they're naturally going to have trouble with that policy absent great care with specifying exactly what gets collected. The "fix" here seems to have been to update their policy documentation to describe exactly that.
It works, but it scales badly.
this does not scale well either
More importantly, Google told him that he needed to disclose what he was doing, and his response was petulance. You know the type: "I was speeding because I was LATE TO WORK, officer!"
Further discussion in this comment thread: https://news.ycombinator.com/item?id=31434975
That seems more than reasonable to me (off by default, with a warning!), and would be exactly what I would expect the app to do if I did enable favicons.
Still pretty bad, and I don't think Google is wrong to flag the app because of this.
However, Google didn't say "if the user enables a certain setting, your app is uploading domain names from your users' contact list to third party avatar services", it said "you're uploading contact list information without disclosing that in the privacy policy".
They seem to know exactly what the problem was but described it in such a vague way that it definitely reads like an accusation of extracting data.
Both are wrong here, but Google is in a position of power and should be held to a higher standard. I'm sure just listing the hostnames that weren't covered by the privacy policy were enough to prevent this whole situation.