I'm having the same issues as you all again. For a long time with ATV 2.0, my 3 Apple TV's would drop off the Devices list. Then, a few months ago or so, everything just started working perfect, no problems. Then, a couple days ago, randomly, all 3 dropped off iTunes again. Two are wired, one is wireless - so I know it's not a wireless problem. I've tried restoring to factory defaults, rebooting everything (iMac, AEBS router, ATV's) - nothing works. My firewall on the iMac is totally open. The wireless one and 1 wired one will sometimes connect long enough to sync immediately following a reboot of everything, but one wired one just won't. I tried removing all 3 from iTunes > Preferences > AppleTV. No luck. I can get the one that won't connect at all to finally show up in Devices this way, but it just gives the "port 3639" error and won't sync at all. The other 2 will only show up after a full reboot of everything. It only seems to have started having problems again after the 7.7.1 iTunes or 2.1 ATV update. Each ATV can play trailers and podcasts, so they are connected to the network OK.
I don't know why this is a constant source of trouble for Apple. I love their products, but this has been an issue since Day 1 of the 2.0 software and I just don't understand why they won't fix it. So frustrating. I'm almost to the point of selling all 3 and getting something different. And that means a lot coming from a fanboy like me. If anyone's got any fixes or knows someone at Apple that can help address this one and for all, let me know.
More details in my archived post on this issue:
http://discussions.apple.com/thread.jspa?threadID=1416066&tstart=0
EDIT: OK, so I took one of the wired ATV's and changed it to wireless. Now it's syncing. Don't know for how long it will last, but it does. There's got to be something messed up with the IP drivers. Hmm. in the middle of syncing, the ATV just randomly put up what looks like a dialog box that says "Apple TV is syncing with Tunes" (never seen that before), and then goes to the Apple logo - but I guess didn't reboot since it's back at the menu and syncing again. Or so it says. Wait - same thing - dialog box thing and then Apple logo for maybe 5-7 seconds. Back to the menu and syncing. Seems like a loop of some sort. Will try rebooting the ATV. OK rebooted. It's in Devices. Claims to be syncing again. Dialog box on ATV again. Now it's actually copying data over. Let's see how long that lasts for... Yeah, so, it copied over 25 pictures, then I got the dreaded "port 3639" error again. Wonderful. And it can still go out to the net and play trailers and podcasts, so I know it's connect to the network OK.
VERY FRUSTRATING. FIX THIS APPLE.