I believe you have to go to your google account. Go to security and click on apps and websites under account permissions. Then you create a password for the apple TV. I think having to do this has to do with not being able to do 2 step authentication with the apple TV.
Anyway, this is what worked for me. I'm obviously not 100% certain it will work for you. You may have a different issue than I did.
Give it a try.