I have exactly the same problem with an Apple TV 3, tried rebooting and even resetting (at least 10 times) but no joy.
It is on a wired network that has no known problems.
Keep getting messages there is an upgrade available but it fails to install (can't install via check for updates either), and in settings, general, about - it says activation - failed.
Any help appriciated.
If you are running 5.1 software and have a wired ethernet connection to your LAN, there is a bug that prevents certain routers from working properly. The easiest fix is to disconnect the ethernet cable and connect to your wireless network.. The bug is fixed after you updatet to 5.1.1, so can reconnect your ethernet cable after the update.