I have the same problem. It began when I updated to the latest version. When I noticed that in my apps there was an "old" Skype, I put it in the trash. From that moment there was no more video. I tried trashing everything and then redownloading. Still the same... no video. However, there is video on Facebook through Skype, but the problem still is there for non-Facebook contacts.