It would be useful if people went to their Google Account page, clicked the Security tab, then tried to access the Two Factor Auth page and reported back what options they had to authenticate. Do you have options other than "enter a two factor auth code"? Can you authenticate on that page with SMS or a backup code?