I am so frustrated. The new AppleTV did not fix this.
It's hard to figure what's gone wrong. There have been an increase in this type of complaint recently from Mac users along with the port 3689 error problem. I'm wondering if the last iTunes updates introduced a new problem, although I'm not experiencing it myself. There must be some combination of factors at work here.
One thing I would suggest doing is to use Internet sharing to connect your ATV directly to your Mac and see if that makes a difference. If your Mac is connected by wifi, set Internet sharing from AirPort to Ethernet and connect your ATV to it by cable. If your Mac is connected by Ethernet cable, set Internet sharing from Ethernet to AirPort. Once that's done, run the network setup again from the ATV so that it is connecting to your Mac.
If that resolves the problem, it would indicate the problem is on your network. If that doesn't resolve the problem, it would implicate either iTunes or your Mac. If it's a problem that's not resolvable by the user, you need to bug Apple support until they get a handle on it.