Is there any chance, that your telco provider is cock blocking video stream?
After being on this forum for a while, I read about some of the weirdest things done by providers, so I wouldn't be surprised.
Secondly, you could try moded version of Skype from XDA. I have been using that version since its release, on my S2, S3, Note and Note 2, now S4, without any problem. I get good video whether on Data or Wifi.
The moded version comes with extra "advanced" setting menu, among many, one which allow you to control the quality of video. From super low to full HD.
You could test it to find out, whether it's related to signal strength.
Do you guys use any similar apps that could effect skype performance?