This seems to be quite a common issue (there are already a few threads about this), but I've yet to see a real solution.
Does this happen with all contacts or just one or two? What version of Messenger are your contacts using?
This problem seems to occur more often when one contact is using the latest WLM and the other is using a previous version (for example. 8.5) so its a good starting point to check that this isnt the case.
If you're both using the same version then i'm not sure what the problem is, but in my experience a video call will work even when webcam doesnt.
Hope this helps