only contacts with recent skype version and a webcam at their end will show video call option on n900. IIRC, as of PR1.2 mac users didn't work either but I don't know if that is still the case. Do a search for the minimum desktop skype version that allows n900 video calls, it's been posted on forum many times.

.EDIT lack of 3G would make video calling pretty pointless - test on wifi to verify that it works with a given contact & then try again with GPRS. i suspect you will still get the option but it won't have enough bandwidth in practice.