Ah, you're a victim of the dreadful: "We were unable to sign you in to .NET Messenger Service, possibly because of a problem with the service or with your Internet connection. Please make sure that you are connected to the Internet. 0x81000301"

#1 Changing your password

I encountered this error myself last night and I must admit it was a bit scary as if Alzheimer kicked in already and I completely forgot my password. So what I did was change the password at Passport's Member Services. I had been signed out of my Passport account and the same, correct password was also being denied! So after answering my Secret Question I was finally allowed to change your password.

That "passport password" combo did the trick for me, but I can imagine there's more to this error than just that, so feel free to comment.

#2 Quick Delete and Fix Attempt (by Jonathan Kay)

Even just trying this solution you will lose all your custom emoticons and display pictures. We recommend backing up your personalized images using the CE/DP Manager before advancing.

Important: Close MSN Messenger completely until the tray icon is gone.

- Windows 98 or Millenium users

1) Click Start > Run
2) Type: %windir% and press enter.
3) Open Application Data and then the Microsoft folder.
4) Right-click the MSN Messenger folder and delete it.

Note: if you're using Profiles with Windows 98/ME, you'll need to go to the Profiles folder, choose your username and then go to the Application Data folder (then continue with the same
process).  If you don't know if you have Profiles setup, most likely you do not (if you don't have Profiles folder in the Windows folder, then you aren't).

- Windows 2000 or Windows XP users
1) Click Start > Run
2) Type: %appdata%\Microsoft and press enter.
3) Right-click the MSN Messenger folder and delete it.

Now restart MSN Messenger and try to sign in again...