I also encountered this.
I fixed it by not running:
sudo google-authenticator
Make sure you are logged into the user you want for ssh, and just run:
google-authenticator
The hint came from this line:
"Do you want me to update your "/root/.google_authenticator" file? (y/n)"
which should have said:
"Do you want me to update your "/home/[your user]/.google_authenticator" file? (y/n)"