Can't connect when calling other computer

When atempting to call a friends computer, or when he attempts to call me,
Live Messenger just hangs at "connecting". Both computers the ring when
called, and on both, the answer & hangup functions work. Text messaging
function works etc. We have lowered firewalls, turned off pop-up blockers
etc. The mic & headphones are working properly. We have had to go to the
the brand x messenger, which works, but its terrible for trying to talk back
& forth on. Can anyone offer some advice?