The title is inaccurate here: they didn't add ads to the paid app, they added recommendations for other games made by the same company. The original title, with "ads" in quotes, is more appropriate.
I am looking at my paid version of Angry Birds. It contains ads for Angry Birds plush toys, an original CD, and St. Patrick's Day cards, just to name a few items.
I bet when a company asks you if they can contact you with "special offers from our partners" you always say yes because they didn't call them "ads"
They're still accurately called ads, though.
You are right. I did not intend to mislead when submitting.