Apple and Facetime
Like most people, I've not been a particular fan of video calling. The only time I've used it myself is on Skype, mainly when I've been abroad.
But a thought on FaceTime: if you really wanted to start eating the mobile operators lunch, whilst still working with them, a good place to start might be to roll out unlocked devices with tariffs that involve no loyalty to any given operator (iPads), and that switch really easily to wi-fi when they can (iPad, iPhone), to further reinforce the perception that operators are "the bit of the mobile experience that breaks all the time".
You could probably roll out a service that operators have consistently failed to get traction with (like video calling), without getting their backs up - how can they complain about your moving into an area that they've failed in and that generates them no revenue? You could do it on wi-fi first, but of course if operator networks ever improve (and like most things, they probably will), it'd be easy to move to 3G/4G - and there'd be no real rush for that, because most of the use cases for video calling involve being at home or at work. Once you were happily doing video calls, dropping back to supporting voice really wouldn't be such a big deal. And I suppose you'd want a mechanism for doing messaging between devices (like push notifications, say) which was independent of operators too.
Jeepers, the folks in Cupertino move fast. How long before iChat (notably missing from the iPhone to date) starts to compete with SMS? "Buy an iPhone and never pay for texting again" would be a pretty attractive offer for some folks.