I was also having this problem, after looking around in Windows Live Messenger, I believe I found the problem. To fix this problem, follow the step by step instructions below:
1. Open Windows Live Messenger
2. Go to File - Tools - Options
3. Click on the privacy tab
4. You should see "All Others" *Shown Below* in the "Block List", highlight "All Others" and click on the "Allow" button. *like shown below*
1. Open Windows Live Messenger
2. Go to File - Tools - Options
3. Click on the privacy tab
4. You should see "All Others" *Shown Below* in the "Block List", highlight "All Others" and click on the "Allow" button. *like shown below*


