I've been having the same issue. There seems to be a number of topics on the apple forums about this same issue. It looks as if there might be an issue with certain routers or certain router setups.
My guess is it has something to do with Bonjour and how the devices find each other. On my setup whenever I try to change any of the sync settings in itunes(turn on/off movies, photos, music, etc), the Apple TV suddenly dissapears from the list, and the only way to get itunes to see it again is to restart itunes, powercycle the router & Apple TV.
I am hoping Apple sees it as an issue and issues a software update, I've tried for 2 days to get it to sync and haven't been successful, the odd thing as that many others with the same router(wrt54g) seem to have it working, I've reset the router to factory settings, turned off all firewall options and still nothing.