This is less of a step-by-step tutorial and more of "this is a situation we encountered and what ended up fixing it... your mileage may vary" post.
We had one laptop that had trouble connecting to one Apple TV in a classroom. My own laptop could AirPlay to it just fine.
When the non-connecting laptop would try to connect, sometimes there'd be an incorrect password error. Other times it would seem to connect (as extended display) but then not actually display. Trying to change from extended display to mirrored display would just keep it on extended display that wasn't really extending to the Apple TV.
I double-checked the Apple TV software was up to date. I rebooted the Apple TV. I rebooted the laptop. I tried taking the password off of the Apple TV AirPlay. No change after any of that.
Then I tried changing the broadcast name of the Apple TV, and the previously non-connecting laptop was able to connect! I changed the name back to the original name, and the laptop could still connect. I added the password back in, and the laptop could still connect.
So, I don't know if the renaming and naming back method will work for others experiencing AirPlay connectivity issues, but it's worth a shot!