Comment by adi_kurian

I had some experience similar to this and found that after some months, when logging in on an extremely familiar to Google setup, that there was an additional prompt where it asked for some old passwords IIRC and then let me in.