I started having this problem of not being able to connect to the gmail smtp to SEND mail from Apple Mail about 3 weeks after setting it up and having it work fine. I have SCOURED the internet looking for solutions. What has finally worked for me is alternating between enabling the 2-step verification and turning it off on my gmail account. First, it won't work, so I'll set up 2-step verification, enter the "special" password into my Mail preferences, then it will work. Later, it will not longer work, so I will disable the 2-step verification and then it will work. Go back to the beginning loop and start again.
had similar issues. But incoming worked fine immediately, only outgoing was an issue.
(Though on iPad + iPhone both in- and out-going mails worked fine.)
I generated a password via Google only ONCE for may Mail app. And I entered it only ONCE in the settings. No other changes done.
So on the Mail application, I saw e-mails coming in. My outgoing e-mail stayed in my "outbox".
I just switched to another outgoing server. In my case, when I opened the advanced settings, a popup screen showed up with a number (approx 10) outgoing servers, all named exactly the same: "Gmail" ;-)
The one that was selected had the message "off-line" behind it and so were a couple of others.
As soon as I picked one that was apparently on-line, the mails in my outbox were send within seconds ...
So problem solved without actually really changing settings or entering paswords.
Hope this helps