So, this morning, my phone was locked out after many wrong lock pattern entries.
Phone was asking for gmail username/pass. For some reason, it was not accepting the correct username/password.
It was relief when it occurred to me that I had two step verification enabled.
I disabled the two step verification from my PC and was able to log into the phone :)