Both iTunes on Windows 7 and the Apple TV 3 are updated to the latest versions. My PC is connected to the router via Cat 5 and the Apple TV is connected on wireless. I can AirPlay with my iPad or iPhone. I've had this work just fine before with other computers. Home sharing is enabled on both devices and connected to the same account with the correct password. I can't figure out what's going on.
The problem could be with your firewall. You should check the firewall software you use and open relevant ports. Some firewalls actually have predefined rules for the services, but for most you'll have to define them manually.
Most commonly the services used are named mDNS or Bonjour sharing. If these aren't found, you can find a list of relevant ports here and add them manually.
I had a similar issue with my Mac and Apple TV
I was able to exchange it at a Apple store after creating a case with Apple support. Info on the exchange program here.
For me, everything worked on the network except for Home Sharing on the Apple TV. It passed all tests and otherwise worked fine. In my case, restarting iTunes would 'enable' Home Sharing access from the Apple TV for a little while, then it would drop again.