Q: apple tv does not recognise new password

Try resetting your Apple TV:

Restore your Apple TV (2nd and 3rd generation) - Apple Support

Hope this helps!

If the Apple TV is not connected & authenticated with a internet connection, you will not be able to connect to iCloud ,  iTunes or anything. You will probably just see Computer & Settings.

Check your IP address Settings > General > About.  it will start with DHCP. if the following number is 169.xx  or blank you are not connected to the internet.

This sounds like an issue with incorrect WPA2 key aka Wi-Fi password. To test this try forgetting your network on another device and signing back in. If the other device is rejected then you know the password is incorrect.  

there are several passwords

the wifi encryption password

the appleID (iCloud) password

the shared itunes lib password

are you 100% you con't confuse any of them and that is the issue ?