I had the same problem on both my iPhone and Mac, after changing my password on my g.xxxx.edu google apps account, used by my university. I could go to system preferences and try to update the password for the account as prompted, and the authentication appeared to succeed, but I got the "Failed to authenticate with Google" message when I tried to accept the management of the account by Google. There was stale data in there somewhere. Both devices failed. I could use the Gmail app and the web interface, so I knew the account itself was ok.
Here is how I finally resolved it.
I went to Settings->mail
I deleted the account from the mail app on my iPhone. Attempting to re-install as a Google email failed (no message on the phone, but I knew why from
the message on the Mac). But it may not have been necessary to delete the account (see below), so try leaving it there.
I installed a new account from the settings->mail page on the phone via "other", putting in my username, thatsme@g.xxxx.edu and the imap server as
imap.gmail.com, with the username thatsme@g.xxxx.edu and the password, and the outgoing mail (smtp) server as stmp.gmail.com, username blank. If needed, the imap port is 993 with SSL and the smtp port is 465 (this is needed, it has to be changed from the default).
This information can be seen by opening your Apple mail app on the Mac, right clicking on a Google account, and clicking on "edit account".
The iPhone was able to verify the data and create the new account.
Then I was able to successfully enter the new password and complete updating the mail application on the Mac. Evidently the manual configuration on the iPhone cleared the stale information at Google and the process could complete.
Unfortunately, the smtp.gmail.com outgoing server rejected my username at g.xxxx.edu. However, I was able to go back to the settings->mail screen and successfully reinstall the thatsme@g.xxxx.edu on the phone as a Google account. I deleted the not-quite functional account that I installed manually.
Now the Apple mail apps are working on both the Mac and the phone.