Yup, have the same issue, went with sms-version because of this ;(. Google Authenticator on HTC Desire HD with custom ROM

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.