That sounds exactly like direct advertising, promotion or direct marketing. Mentioning you have a new feature isn't any of those things. Advertising a daily offer? That's definitely one or all of them,

When I get a notification via Google Plus app, driving me to their app because there's something that I've expressed interest in, is that "advertising, promotion, or direct marketing"? Or from a Facebook app? Or any game informing me it's my turn?

Yes, they drive app use, and perhaps even later revenues, but in a way that's in harmony with my intent when installing the app and expectations. It's like "you've got mail (that you requested)". You can squint and call it marketing, but then almost every notification that increases use of a profitable app is also marketing.

Yes. From the developer agreement(which is more explicit than the submission guidelines), pretty much every app violates this:

2.2 You may not use the APN or Local Notifications for the purposes of advertising, product promotion, or direct marketing of any kind (e.g., up-selling, cross-selling, etc.), including, but not limited to, sending any messages to promote the use of Your Application or advertise the availability of new features or versions.

Thanks for that pointer. I'm surprise that highlighting new versions or existing features is prohibited. I've received quite a few such messages from major apps -- Zynga, Facebook, other leading games. Are they all being kicked out of the App Store?

I was once tasked almost word-for-word in violation of this(at a small company). I argued and quoted and the executive response was 'everyone else is doing it so we'll do it until we get caught'

Yep, just like uploading the entire contacts list. Everyone did it until they got caught.