I had this problem too, then discovered that if I had Photobooth open then the video wouldn't work on skype. I closed photobooth and like magic the video call worked!
I am having this same issue, everyone I skype with has a Mac - at least everyone I have tried to video chat with so far. I am unable to test it on a PC or iPhone/Android since none of my friends have one anymore.
My friend is using the the 2010 model MacBook 13in running Snow Leopard 10.6.8, the latest version. She's connected via ethernet cable, the latest version of Skype for Mac (version 5.8).
I have tried my Vita both over 3G and WiFi. My Mac connects with video via the same WiFi network no problem with Skype. What do you think could be the issue?