I know that people love to wet themselves over all the features the iPhone 4 might have (that other phones have had for years, no less), but it should be said that the UK's 3G networks have been doing video calling for years. It was the first "killer app", if you will.
No one used it because a) the 3G coverage sucked back then (and it still does on o2), b) they want 50p/min for the privilege, and c) it was a bit gimmicky.
I have had a video call capable phone for years. I don't use that feature, mainly because of the price. I'll just use Skype.