I had something like this happen becasue I was logging in to some microsoft service, and thought I was supposed to be giving them my microsoft account password but apparently they wanted my gmail password for whatever they were up to. And doing a password reset on this microsoft service actually reset my stupid gmail account. Then once I figured out what happened, google wouldn't let me use an old password to set it back.