Apple TV

Hey there, I have a few questions about the scenario. Is it happening with every MacBook you have, or just one in particular? Are they trying to use AirPlay for audio or AirPlay Mirroring? If the latter, have you verified that the MacBook is sufficiently new enough to support AirPlay Mirroring? Thanks!

If it's a newer Apple TV (3 rev. "A") which has the latest update and relatively new iOS devices, it may be connecting directly via Peer-to-peer wifi instead of going through your network. Only a relatively recent MacBook running Yosemite can connect peer-to-peer to Apple TV, and there is no real indication when connected whether you're connected peer-to-peer or (the traditional way) through your network. This is all to illustrate that there may be a big difference in how reliably the devices connect. I have found the new peer-to-peer functionality to be a better, faster connection, as long as you're close enough to the device (~<30 ft).
Are the Apple TV's connected to your network via ethernet or wifi?

Wifi, and it happens to a few macs, I brought mine in and it did the same thing

I would start by verifying that the MacBooks are new enough to use Airplay Mirroring. The following link is for the mirroring requirements: http://support.apple.com/kb/ht5404

Are you getting the error when trying to play audio or when trying to mirror? Or both?

It would be relatively simple step to connect the Apple TV(s) to ethernet and test the same Macs. Also easy to try is to turn on Bluetooth on an affected MacBook, if it is off. That has been known to cause issues.

Then I would probably list the specs of the Macs which have the trouble vs ones which don't and look for commonalities.

Had similar issue. Changed resolution on Apple TV from auto to 720 P.
It may not help with your issue. Ours was dropping connection after being connected to for short amount of time. Issue was with OS only, not with iOS.

These are new macbooks, they were purchased in July/August.

Do I understand correctly that some of these new machines work, and some don't? If so, then I definitely advise evaluating commonalities such as OS version and Bluetooth status. Also might be a good idea to click the wifi icon with the option key down on each Mac and note which AP the device is connected to ("BSSID"), the network name if it varies, and whether it's a 2.4 Ghz or 5.1 Ghz channel. If you compile this with the "works" or "doesn't work" data, you may find a correlation and an answer to your query.

Well we figured out the issue, and it was not the computers. Our network reset and peer to peer was blocked. Sorry about starting this thread!