Skype Camera on Android
I find Skype to be very poorly optimized, especially for video.

Maybe you should try other alternatives to Skype for video like Hangout or Tango? Just to be able to see if you will be getting the same issues as you do with Skype. If you do, then it means you have issues with your network.