Windows Live Messenger Problem

Hello, Lately I have not been able to add any contacts nor receive any notifications to be added to my friends contacts list when they add me. When I add a friend using the Add a contact button in windows live messenger, the screen stalls at the "Adding blahblah@hotmail.com" screen and after a while it a message appears and says "You're done! This Windows Live Service isn't available right now but we'll add your contact as soon as it is available again. You don't need to do anything else." But I have been waiting forever and I know for sure that my friend has added the correct email but I still dont get any notifications nor do they when I add them. How do I fix this?? I've tried re-installing, cleaning my contacts cache, optimizing my browser (deleting cookies and all that) but still no luck. Can anyone help me? Thanks