Hi igalst, sorry if I'm guilty of pointing out the bleedin' obvious:

Check that your phone IM status is set to Online (green dot in status bar) and you are logged into your Skype account (green dot next to Skype service entry).
Check that your recipient's status is Online and they have a webcam setup & activated for their Skype account.
Look at the listing for your recipient in Contacts to confirm their status is Online with a green dot next to their entry.
Choose the contact and scroll almost to the bottom of the contact options where you should find Skype video call option

I can only get it working on my N900 via WiFi. T-Mobile seem to be throttling my attempts at Skype video calls over 3.5G