From my view, it's a problem with your account in the messenger servers. Instead of (or appart from) accepting the pop up that says they've added you, try to add them yourself, using the menu Contacts > Add new contact.
If that doesn't work....
quote:
Originally posted by PunkBatman
I've already emailed their support guys.
...that's the only thing you can do