Why can't I add a contact to my MSN account?

I can't add a contact to my MSN account... as soon as I add it, it appears in the contact list as 'offline' for a few seconds, then disappears, never to be seen again. My contact also doesn't get a notification that I added him, so we can't actually talk....