Are you using version 2.5? If so, downgrade to version 2.0 - the video feature was broken for many users in 2.5 in exactly the manner that you describe. The only known fix at this time is to downgrade back to the old version.
---------- Post added at 15:06 ---------- Previous post was at 15:01 ----------
See here:
http://forum.skype.com/viewtopic.php?t=54411&highlight= for more details on the problem. You can download the older versions from
http://www.oldapps.com/skype