I too have had a similar issue with syncing Gmail with Mail, Mailbird, Outlook, Spark and several other clients. This is what worked for me.
- Go to the web client (https://mail.google.com/mail/u/0/#all) mark All of your email as Read - to do this use the small drop down arrow next to the refresh icon. Note. when you have selected All you will see another selection just above the email subject heading that reads something like this:
"All 100 messages on this page are selected.Select all xx,xxx messages in All Mail:" where xx,xxx is the total number of emails.
Click the underlined text to ensure that All of the mail 'really is' selected
The More menu has the Mark as Read option
- Go back to your client: Mail, Outlook etc and try setting up and syncing the email account again
- If this fails go back to the web client, select All Mail again and then Archive them. This is that small square icon with a downwards pointing arrow; don't worry you'll not lose any of your emails. "It's Google - they don't delete anything!"
- Go back and try your Mail clients again.
Hope this helps!
p.s - you can view all of your Archived Emails by clicking the 'All Emails' label/menu
p.p.s - It had nothing to do with 2 factor Authentication, that was a red herring