I ran into a similar issue. I think you are experiencing two problems simultaneously.
The first problem relates to Mail not meeting Google's standards for security. The only way I've found to get it to work was to "Allowing less secure apps to access your account" a way to do that can be found here.
The second problem, I assume, you're having is you're attempting to set up a Gmail account via the Gmail option from the pull down menu. I've never gotten Gmail to set up properly that way. You'll need select the "Other" option, I believe it is, and set up the account manually.
The server settings should be mail.gmail.com