Or, if you have never setup a password on your AppleTV, you'll also get this error. I experienced this the other day. It was a very simple fix, I added a password to my Apple TV, then logged in, with no problems.
It's not the same as your iTunes password and such.
Sent from my iOS ecosystem!