I don't have enough reputation to comment, but I want to add my own experience on when I've "found" the issue...
I was setting up a new email client Airmail 2.0 to use Google's SMTP server to send mail on behalf on a Gmail account.
Now, my setup might not be too "common": I have this specific Gmail address forwarded to a different address, which is the one I'm using from Airmail, and I'm setting the gmail address as an "alias" of that account. Likely to avoid looking like Spam, Airmail allows to configure a specific SMTP server to use when sending "from" an alias.
I have another Gmail account set up on Airmail without any "funky" configuration or redirections, and that one is working fine (no messages about "reduced security", for example). So I copied the SMTP settings from the "normal" account to the new one:
These are the settings for the "classical" account:
And these are the ones for the "alias" SMTP server:
Notice any differences? Me neither!!
I've been having a look around, and I've also found the page mentioned previously, Google's Security article New Security Measures Will Affect Older (non-OAuth 2.0) Applications where the change is announced - this paragraph (emphasis mine!) seems to imply that apps will need to be "authorised" to access to the account in similar way as many other "app clients" (Dropbox, etc) do:
That's why, beginning in the second half of 2014, we'll start gradually increasing the security checks performed when users log in to Google. These additional checks will ensure that only the intended user has access to their account, whether through a browser, device or application. These changes will affect any application that sends a username and/or password to Google.
I'm not against the idea, by itself, but I'd appreciate having more info what apps need to do to be considered safe so we can ask our app providers to implement the necessary changes...
More info on the topic here: GMail starts to block less secure apps: how to enable access again.
What is more puzzling is that my "other" Gmail account doesn't trigger this type of messages, as I don't have 2FA enabled so according to the previous article I should've got some of those errors!
UPDATED 2014-12-31, 17:52 GMT: Out of curiosity, I've checked the settings for my old Gmail account, and I've seen that it's actually set to "less security" (as Google calls it). I guess that when Google introduced the feature, the default for existing accounts that are being accessed by "less-secure" (as per Google terms) clients, is to allow them to keep on being accessed.
On the other hand, as some of the comments on the original Google Blog Post say, it's great that Google worries about our security, but the could have started by supporting things like CRAM-MD5 or DIGEST-MD5 for authentication instead of just plain LOGIN.