There are some compatibility issues with the new Windows Live Messenger 2009 and webcams.
Find out which versions of Messenger your contacts are using as this could affect it.
Also have a
search through the forums as this question has been asked a number of times before and some possible solutions posted (which i can't recall off the top of my head)