Сам спросил - сам ответил.
Время на Андроиде, где стоял Google Authenticator, немного отличалось, буквально на минуту. Поэтому код не совпадал. При этом проверка на gmail, видимо, менее строгая, поэтому, проверяя работоспособность на gmail - все работало и я не вспринимал телефон в качестве возможной проблемы.
Сделал менее строгую проверку у себя - теперь все ОК.
