To shed more light on the subject, I have been fighting the port 3689 not open issue as well and I have had hit and miss ideas in figuring this out.
At one point, I thought it was the service (i'm on windows xp) called "apple mobile device" or something like that. At one point, restarting itunes AND restarting this service seemed to remedy this, albeit temporarily.
At another point, I was (and still am) thinking it is my kaspersky internet security suite since disabling protection seems to allow communication between itunes and

tv for only a little while.
I have read that it might be possible that there is so much traffic going between itunes and

tv that either the router, or the computer itself is having (bandwidth?) issues, or issues keeping up with the traffic itself. Some people have said that having torrents running or some service from realplayer is creating too much traffic that itunes can't communicate with the appletv.
Some have also stated that some routers just cant stand the amount of traffic from one device to the other and something along the way gets messed up. A change in routers have sometimes remedied the issue (permanently?). A trend I noticed was moving from linksys to netgear sometimes fixed the issue.
Some have stated that interference (like from a near by microwave cooker) could cause this issue as well as it's disrupting wireless comm with the appletv and itunes.
Last night, I was starting to think that it was the Apple mobile device service again since communication between itunes and

tv was disrupted again not long after i plugged my iphone up to my computer that was syncing some 1500 songs to the appletv. The appletv reached about 500 songs and stopped. I got the firewall error. Restarted the apple mobile service, and itunes, and had my iphone unplugged and things picked up where they left off and completed the sync of my music.
It's totally hit and miss on figuring this thing out. Last night I managed to sync a movie to the appletv, with kaspersky completely disabled, appletv setup as static ip, port open on my linksys for 3689 for my appletv ip, my iphone was not plugged in to the computer at the time and I did not have anything utilizing heavy traffic while syncing was in progress.