Hi, We were having a similar problem. My wife had changed her Apple ID password, and we could no longer sign in to the iTunes store from our Apple TV 3rd gen. Log-ins worked fine from other devices. I tore my hair out for a couple of hours fiddling with the network settings to get it to work, and it was strange you know, because we could sign in to iCloud from the ATV, but the iTunes store always immediately reported (too quickly really, made me suspicious - I'm sure it wasn't even trying to connect) "Cannot connect to iTunes store.", when we clicked submit for the password.
Long story short, I started to suspect something with our Internet provider (Axtel.mx, a fiber optic accesss provider in Mexico) although we've never had any connectivity problems that I can recall. I turned off the fiber modem & killed the wifi, and connected through Personal Hotspot on my iPhone using my cellular data connection: Presto!! It logged in to iTunes immediately. Strangely, once I had logged in successfully, I was able to reactivate all of the prior network settings and it still works - even though it seems like it shouldn't. So, try logging on from a different network and see if that cures it for you.
