Soweit ich das mal recherchiert habe ist dieses "Port 3689"-Problem nie so ganz endgültig aufgeklärt worden. Von Apple gibt es nur den Ratschlag man solle in der Systemeinstellung unter Sicherheit/Firewall die Zugriffe für iTunes.app extra freigeben. Und unter Sharing auch iTunes-sharing aktivieren. (Diesen Punkt gibt es aber bei mir garnicht...) Ich hatte dieses Verbindungsproblem auch öfter und es schien mir sehr davon abzuhängen in welcher Reihenfolge ich die Geräte eingeschaltet hatte, und auch ob ich die Verbindung über Wlan oder Ethernetkabel herstellte. Mal gings es, und mal kam diese Fehlermeldung. Erst seit dem letzten Apple TV Update läuft das bei alles Fehlerfrei.
Mit Deinem Router hat das ganze aber sicher nichts zu tun, denn innerhalb Deines Heimnetzwerkes wirst Du da keine Firewall aktiviert haben, oder?