I believe it's important that both caller and recipient are on 3G connections and both devices are capable of performing 3G video calling. Often a device will drop down to 2.5G or 2G if the coverage is poor, if set to "automatic"; I'm not sure what happens when one device is on a 3G and the other on a 3.5G connection.

The other thing to consider is local network traffic and overall ability to connect. I have had a supposedly full 3.5G signal and struggled to connect to a commonly used search-engine's front page.

Have you tried trying to make a 3G video call, say late at night when networks are a little quieter, to someone who is both in the same room and on the same network? Doing this would ensure as strong and similar signal strength as is possible.

Some devices don't support video calls without wifi, even though one thinks they might/should do - 'i' 'm not saying anything!

- as an after-thought, do you have any software installed that might conflict with either the front or back camera?