I know there are several guides and fixes out there about this error, but I found a workaround that I couldn't find in any forum or article:

Security Settings \ Local Policies \ Security Options - network security: LDAP client signing requirements

Set that to none in your SharePoint Server... now I'm stuck with the more familiar "Unable to process Create message"... I'll let you know.

-------------------------------------------------------------------------------------------------------------------------------

Update: I installed the recently available Cumulative Update for February 2011 (Foundation, Server) restarted the service (actually this is not yet production env, so I restarted the whole farm) and voilá, I could create my connection.

Remember, the Server update includes the Foundation binaries, so you'll only need one of those.

Please note that changing the Local Policy (LDAP client signing requirements) have further implications, make sure this is appropiate for your environment. I'm investigating wheter or not it's required in my customer's environment and will update this post accordingly.

More info:

• http://technet.microsoft.com/en-us/library/cc738915(WS.10).aspx
• http://support.microsoft.com/kb/823659

Thanks to Harbar for pointing that out!