The default stun server configured in telepathy-gabble seems to be (permanently?) down. Commit 1aca8d2c7 changed from stun.collabora.co.uk to stun.telepathy.im long time ago, but the DNS currently points back to stun.collabora.co.uk IP address.
This seems to prevent video calls between two clients which are both behind NAT. Is there a workaround for this? I cannot see a way to manually set the STUN server used by, for example, empathy.
If both peers are behind an uncooperative NAT, then you need to setup a turn server to relay the media streams. I suggested some patches to telepathy-gabble some time ago: https://bugs.freedesktop.org/show_bug.cgi?id=93972