Iíve done a fair amount of video calling over 3G. Mostly by tethering my laptop to the phone, but also some directly on a (non-Pre3) phone.
Basically, if you have a strong signal you will get decent results, but expect to still get a fair amount of temporary freeze-ups and the like. If your signal strength starts to drop, youíre going to have significantly worse results. At which point youíre better off just switching to audio only.
Best results really, are to place the phone outside (where it will most likely get better reception) and wifi tether to a laptop/tablet inside to make the skype call.
In addition, before making a call, it doesnít hurt to run a couple of speedtest runs to find a spot where you get the best network throughput. Even moving around a building or room some can make a fair difference.