Something that I have learned, our new Samsung phones, Note 5, S6, S6 Edge etc.... if your phone will not let you log in reset the phone not your google mail account. If you do so you will not be able to setup your phone for 72 hours. Google set this up in case your phone is stolen. Now I would like like to start a petition against this measure because this measure do not take curtain situations in account. What if you are in a emergency and you can not call for help and you changed your gmail account password trying to troubleshoot your non access to your phone. You are going to be stranded or lose a big account that you might have been working on at work because you can access your phone for 72 hours. I do not see what gives the the right to do this, we pay enough for insurance to protect us from theft and damage. Is there anyone that feels the same way?
Whatever you do do not change your password on your google account.
Trying to understand what you did, my new Note 5 would not let me access it after a reboot after locking up of transfering pictures to my daughters shared folder on Google drive. It would not except my finger print, my backup password, or verification using Google account. I thought my gmail was acting so I grabbed my laptop and when to gmail, worked fine. I think said well I can not get into my Note 5 still, let me change my password on Google mail and log back in, my computer worked fine, i was in gmail. When I contacted T-mobile the tech told me I'm sorry you will have to contact Samsung because all they could not is reset the phone. Called Samsung they said i will have to reset the phone. So we did but I could not finish my setup for my phone, Google would not setup, Samsung tech asked me did I change my Google password earlier? I told her yes I did to trying to troubleshoot why it wasn't working. She said Google has a new security thing now you reset your phone and your Gmail account you wait 72 hours to be able to setup up your phone. That sh*t stinks, so stupid, all you need to do it tell them the most go to their carrier and verify themselves and they unlock the phone.