Are you trying out the current Windows Live Messenger Wave 4 Public Beta? You might receive the error code 81000395 when you try to sign in. The Windows Live team has published a workaround for this error code. A permanent fix will be included in the Wave 4 Final. Here is the workaround:
- Open Windows Live Messenger, and wait for error 81000395.
- In the sign-in window, click the Forget me link.If you use multiple accounts on that machine, you should only need to click (Forget me) for the account that is causing an error.
- Retry to sign in to Messenger by entering your Windows Live ID and password.
Does this work for you?