Does one of you, by chance, have a Linksys wrt54gv 802.11g router? A friend had one, and no matter how we configured the ports, we never could get it working properly. It's been a while, so I don't remember if/what the final reason was.
He's become a BIG switcher and just went ahead and bought an Apple Airport Extreme Base station. He got tired of playing with the Linksys.
I know it's not a generic Linksys problem, as I've used video ichat on other models of their wireless routers. (and, I've used video ichat with a bunch of other non-apple wireless routers without problem).