If it isn't your Firewall settings, what kind of router are you using and does it use UPnP?
If it does, try toggling UPnP off and on again, then connecting. Also, you might want to try using a different MTU setting. The Ralph Johns site has some recommendations on values to use.
This happens to me with my brother and toggling the UPnP solves it (Netgear D834G router). However, if I turn off or reboot my router, I have to toggle the option once more to get video chats working again. PITA.