I have the same problem with 2 Apple TV2 (1080p version). I have iTunes on a mac mini and on a Windows PC. My router is an airport extreme and all my deices are wired (i.e. I am not using the WiFi). Based on numerous posts I have see on this and other forums, here is what I have tried.
-restart Apple TV: does not work
-unplug and plug back in Apple TV: does not work
-restart iTunes: works 100% of the time
-restart computer: works 100% of the time (think this is related to restrt itunes)
-Play movie, TV show or song and itunes and use Apple TV as another speak: works 100% of the time
-Do not use WiFi sync on iPod/iPhone/iPad devices: did not work
-Uncheck keep itunes media folder organized: did not work
Observations
-Netflix, itunes store, itunes match all work only library functions are locked
-Remote App on iPad/iPhone cannot connect to itunes library either
-notice 75% of the time I need to restart iTunes 1/day and everything is fine as long as I contineu to use the device. Once I cease using the Apple TV, it may or may not be connected to the library.
-when Apple TV cannot connect to one library, it cannot connect to any (i.e. I was stuck on loading with my mac mini and PC).
-other server (non-iTunes) applications I use on the mac mini still work when Apple TV does not. One example is logitech squeeze server and air print activator,
So in my case, I just need to retsrat iTunes prior to using AppleTV. Personally, I use a VNC viewer on my iPad to do this so I do not even need to go to the computer. I do not like the solution but I am able to use my Apple TV. I just wish Apple would develop a solutioon that works.