After I had installed the Outlook Hotmail Connector for Outlook 2010, the following error occurred when I tried to add my live.nl (Dutch LIVE account) to Outlook:
The cause of this problem was quite simple but awkward: the firewall was blocking the traffic. So, what I did: I turned off the firewall, reconfigured my Outlook account, and it completed successfully.
Don’t forget to turn the firewall back on again.
Strangest part: I’ve never been able to simulate the problem. Deleting and adding my LIVE profile went flawlessly. :-)
If you get error 0×80041059 while trying to add the account, make sure you have enabled the Inbound rule for Outlook in your Windows Firewall. The inbound Rule for Outlook should allow all traffic over port 6004 for the process outlook.exe
To just make sure the Firewall is the problem (or not), you could choose to disable the firewall temporary. Then recheck again whether error 0×80041059: "Could not authenticate against the Windows Live ID service. Please try again” occurs.