ok so been having this issue for so long and not one of the above solutions ever worked for me. then I remembered I did fix it once and now I finally remember the fix. The issue is with DNS - make sure that your apple tv and computer are on the same dns (i.e. 8.8.8.8 or better 192.168.1.1 (or whatever your router IP is), make sure its not pointing to some proxy or pihole kind of dns. After changing this, rebooting both, works like a charm.