I think you need to check the Video call box in the settings of the Contacts list.
I had it off for a while but people could do skype calls with video with me, but i couldn't do skype calls with video to them.

Hope that helps