1st gen ATV sw upd: "AppleTV can't check right now" after factory reset

After upgrading to ITunes 11 over the weekend, my 1st gen Apple TV no longer appeared in the devices list, but my IPhone remained. I tried several things posted here, but I had no luck.

I decided to try a "clean start" approach, since I have no idea how the detection of devices part of ITunes 11 work (for that matter, I wasn't sure how it worked in previous versions either). Just one of those Apple mysteries we must live with on occasion I guess.

I did a factory reset of the ATV, which caused an issue more troubling and frustrating than the original one.

When the network status per the Network settings screen indicates the ATV is connected to my LAN AND the internet, and I try to initiate any software update, Sometimes immediately, sometimes after several seconds I get a "AppleTV can't check right now. Try again later." message. If not "right now", does that mean it will in 5 minutes,at 3am, next month, when I've said pretty please?

I spent many hours on a Sunday afternoon (which I'd love to have back), trying different combinations of the following, beginning with a factory reset:

1. Ethernet conneciton (to my FIOS router)

2. Wifi

3. Automatic ATV network configuration

4. Manual IP configuration, with verified parameters I have tested on other network devices I use.

5. Dynamic DHCP IP assignment from the router.

6. Static IP assignment on the router via the ATV's mac address.

In each case, the Network screen status was connected to the internet (not just the LAN) before initiating the update. All of my other IP devices on the same router have no problems using the internet via direct ethernet and WIFI.

Must be a firewall problem or something in the router, right? Nope, I ruled that out by doing a factory reset and connecting the ATV to my mobile broadband WIFI network. Confirmed connection to the internet, but no luck with sw update.

Are there any kind souls that can shed light on my dilema?