iTunes library access not consistent
I have sometimes have similar issues accessing iTunes libraries from AppleTVs. Sometimes I have better luck using a WiFi rather than Ethernet connection.

Also, have you tried assigning your AppleTVs static IP addresses (assuming you use DHCP?)