Connecting to MS AD server using Principlecontext Fails with error "The server cannot handle directory requests"

Background

An application was migrated to a new AD Forest and we encountered LDAP errors. This took a long time to resolve.

I increased the logging on the NTDS service on 1 domain Controller and forced connection to that server: 

 00002035: LdapErr: DSID-0C090F40, comment: Fast bind mode can only be invoked on an unbound connection. This connection has already been bound., data 0, v1db1

 We tracked this down to the fact that the users have an autoenrolled certificate that has "client Authentication" as a purpose.

 

Connecting using port 389 - non Secured worked, but wasnt an option.

 

Removing the certificate worked, but was also not an option.

http://msdn.microsoft.com/en-us/magazine/cc135979.aspx