@Andrew_b is ok to state the obvious..
I have followed your steps and I was able to use video call with Skype.

How do I initiate a video call via regular cell call?

I ran a couple of tests over WiFi last week (I have two Skype accounts), and video connection was sporadic. At the moment I have not been able to pinpoint the cause of the problem. What I have not been able to accomplish is a video connection to the OS X Skype client.

Hi igalst, the N900 does not support regular cellular video calls, only this Skype service (or Gtalk) works. As I mentioned earlier, I can't get Skype Video to work in the UK over T-Mobile cellular, it only works for me over Wi-Fi, which pretty much defeats the object ( a bit like iFaceWhatever on the iPhone 4)

Oh... I was sure it works. Anyway it's not a problem as I don't remember myself using this option ever.

In Israel I didn't test myself the VOIP on cellular providers, but as much as I know they do allow you to use those services almost with not capping on their end.
A couple of months ago there was an issue that one big carrier limited or even blocked the usage of VOIP on their network. They have even made new clients to sign this term in the contract. However, the ministry of communication made them stop this behavior.