AppleTV not working with AirParrot or AirPlay from iTunes; works fine with iPhone

So here's my issue - I never used AirPlay to go from iTunes on my MBP to my AppleTV. I use either Homeshare or iTunes Match currently to play my music and movies, and occasionally will AirPlay from my iPhone or iPad to the AppleTV as well. I have two - one from mid-2011, one that I bought just after they released the new ones this month. Both have the same exact issue when trying to use AirPlay from iTunes or use the AirParrot application. I've talked with AirParrot support, and they've walked me through a bunch of steps to try and fix it with no success. Here's what I know:

*AirPlay from iPhone/iPad to both AppleTVs works fine
*Homeshare from my iTunes library to AppleTV works, but will drop without notice sometimes
*All devices are on the same network (CenturyLink DSL through a Zyxel router)
*There are no Firewalls set up on my Mac as far as I can tell

Can anyone figure out how to get my Mac to be able to use the AirPlay feature to my AppleTVs? I figure it has to be a setting on my Mac or iTunes since the iPhone/AppleTV communication works fine.

Also -

I created a network on my Macbook Pro - My iPhone and iPad were able to see it and connect to it, but the AppleTV was not able to.

Well, without doing anything, they finally started showing up.