I use Google two-factor authentication, so I am using application passwords for my devices (namely my phone). To protect my privacy, I disabled the account for my phone when I brought it to the service. While it would have been enough to remove the application password, I accidentally removed access from the device itself. Now Google doesn't allow me to log in even if I generate a new application password for that device. It doesn't say that the password is incorrect, it simply prompts for the password again, saying "Please enter your Google Account password", no matter how many times I type in the (correct) password. I get a different error message if I type in an incorrect password.
What should I do in this case? How to make Google allow me to log in to my phone again?