When I first used Authenticator I had this problem, because the clock on my phone was a couple of minutes out of sync.

There is room for some error but it is worth making sure the time on your phone is correct.