How are these devices connected to the router? Wifi or ethernet or both?
There have been occasional reports of routers keeping wired and wi-fi networks separate.
Do you have any Firewalls enabled?
Any security software that may be blocking communication eg NetBarrier ?
I assume you've enabled Home Sharing in iTunes and on the AppleTV2.
You might try to find the internal LAN IP addresses for each device and see if the are similar bar the last digit and have the same subnet. For AppleTV find in under Settings>About.
For example youur iMac might be 192.168.0.1, the Macbook 192.168.0.2 and the AppleTV 192.168.0.3, with all sharing a subnet of 255.255.255.0 - if they have similar addresses like this it would be a start to at least know they should be on the same network. Next question would be whether it's a software issue blocking comms or a router setting.
Any way you could connect AppleTV and one of computers via ethernet? Either directly ro via router.
Via router would give both internet access and hopefully show if it's a wi-fi issue.
Directly eg MAcbook to AppleTV with ethernet would disable AppleTV wifi and lose internet connection but if the unit could see the iTunes library it would be a step forward. You could enable internet sharing over ethernet on teh Macbook to test further.