This is a short one.
If you have Google Authenticator enabled, Apple TV will not prompt you for that. Instead, you will simply get error on login.
In order to get this working, you need to add an "Authorised Access to your Google Account" for your Apple TV.
Just go to https://accounts.google.com/b/0/IssuedAuthSubTokens and generate a new application-specific password.
Then simply use your same username and the generated password to your Apple TV.
You are done!