Windows Live Messenger not letting me add people

[potterfan3]

OK, when ever I go to add someone on WLM it says "it looks like this person doesn't use messenger yet" (when they do) and they don't get an invite, and whenever somebody adds me I don't get the invite.

The problem seems local to this computer I'm using, as when I use another machine I get the invites. However when I come back to using this computer after I've accepted the invites on another machine they do not show up in my contact list.

I've tried completely uninstalling and reinstalling everything twice to no success. I had messenger plus but that's gone too and it didn't solve the problem.

And no, it isn't because my friends don't like me I've been testing various solutions with another account I have.