Gmail accounts seem to be working (after a wait)
Must be some kind of timing issue with Google security. Initially, I was not able to turn on mail for any of my Google accounts in Internet account settings. After waiting several hours I tried again, and was able to successfully re-add the accounts.
The latest Mac Mail app seems to have problems accessing Gmail accounts. I even deleted my gmail accounts and tried to set them up again, but accessing mail through through Mac Mail is a no go. This is a bit of a showstopper for me.
Must be some kind of timing issue with Google security. Initially, I was not able to turn on mail for any of my Google accounts in Internet account settings. After waiting several hours I tried again, and was able to successfully re-add the accounts.