I tried to log in to iCloud for the first time on my older model Apple TV using the correct password with no success. I restarted, reset(restore), reset(reset all settings), verified the correct time-zone & region format and none of these problem resolution options worked for me that I read online. Finally I decided to try turning off the two-step verification process when Managing AppleID online and I was able to log into iCloud on my Apple TV. Prior to doing that I would receive a pop up alert on my phone indicating someone was trying login to a new device with my AppleID. After selecting allow it would generate a code indicating I should use it after entering my password. I would enter my password & then the code, enter the code first & then the password several times. That's when I suspected the two-step authentication is what was preventing me from logging in. Hope this was able to help you if you were experiencing the same problem.