This has been bugging me for ages, but the fix is so simple. I use OpenBSD for my router, and have PF (Packet Filter) running the firewall and NAT rules. I have previously setup the port forwarding, etc. according to Apple, but never could get a successful connection using video or audio (or screen sharing). After reading a post on the OpenBSD misc mailing list I went back and read the OpenBSD 4.