Had same problem with the new Apple TV, i.e. extremely slow when loading videos from iTunes library. At first the problem was intermittent, but when I bought and installed a second unit of ATV-2 for a second TV, loading times on both units ground to a halt, and remained that way for the original unit even after I subsequently turned off the new one.
Tried rebooting iMac, restarting iTunes, resetting ATVs to factory setting, restarting Airport Extreme — all to no avail. Then I unplugged the Airport Express which I'd installed as a Wi-Fi signal extender in a far corner of the house and voila — problem solved, itunes loading speed on both ATVs went back to normal!
I plugged the Airport Express back in and sure enough, the problem returned.
So now I have to unplug the Express when using Apple TV. Not an ideal fix, trading one appliance for another.