I had this same thing happen to my Samsung Galaxy s5 phone, and searched the internet for a solution. After trying all the solutions I read about, and when none of them worked, I tried going to
mail.google.com ,that was mentioned on one site, on my home computer.
I logged in using my Galaxy s5 email account name, and was asked to send a message to my smartphone, which asks if you are the one making the request. Once I selected "yes," I was in my Gmail account for my smartphone. The reason I went to mail.google.com on my home computer, was to check the Account Type for my account; whether it was imap or pop3. I tried entering my password but found the one I'd written down wasn't the one the system was expecting--my goof in writing down my password. So, I clicked on "forgot password" to enter a new password. Once that was done, I written down accurately, I was granted access to my smartphone Gmail account.
Once the gear on the upper right is clicked on, a drop down menu appears. Once Settings is selected, the main settings for the account can be viewed by selecting whichever heading at the top of the page. Selecting Forward and Imap or Pop3, I think it said, will take you to the page with the imap or pop3 information on it. Clicking on Learn More under either Pop3 or Imap will bring up detailed information for those account types. Since Pop3 was disabled, and Imap was enabled, I clicked on the Learn More for Imap. Once I wrote down port numbers, and other information I wanted to have on hand, I went to my Galaxy s5.
What worked for me, so far, was to delete my Gmail address in the Android Email app, and setup the app as if I had a new account. I entered my Gmail address, the new password I'd change while in my Gmail account, chose Manual setup, but ran into some type of problem--bad fingers on the keyboard, I think. At the Incoming mail screen, I made sure the port number I got from my Gmail account was correct and selected Done. A problem was encountered as the app couldn't authenticate the account and would not go to the Outgoing mail screen. After several tries and receiving the same message, I started over completely. I deleted the Gmail address and password I'd entered, and reentered both again, again selecting Manual Setup. This time the first setting allowed authentication and the Outgoing mail screen appeared, as did each successive screen.
So far, and it's been over an hour, not one notification of "sign-in failed" has appeared. Hopefully it will stay that way.