Is there a signing hierarchy (i.e not self-signed)? "wildcard" and "self-signed" are not exclusive.
A commercial wildcard cert will have a hierarchy, i.e. one or more intermediate CAs, and a root CA.
sha-512 or md5 are hashes used in the cert signature, they are not encryption algorithms. These are used to verify the cert integrity, the cipher used for a connection is negotiated independently of this.
I think the most likely causes are either sha512 (more correctly, "sha512WithRSAEncryption") is not supported in Ubuntu 10; or the machine is missing one or more CA certs (intermediate or root), so full chain verification cannot complete.
You can see if openssl can deal with the server's new cert by running (on the Ubuntu 10 machine):
openssl x509 -in newservercert.crt -noout -text
though that may not be conclusive. This may also be helpful:
ldapsearch -x -Z -v -h your.ldap.server
(There's a slim chance GnuTLS is used instead of OpenSSL, can't help there, sorry!)
You can probably confirm or deny a chain problem by adding this to your /etc/ldap/ldap.conf file:
TLS_REQCERT never
If that helps, you should obtain the missing parts of the chain, and add them to your local store, how that is accomplished depends on the client configuration, checking for "TLS_CACERT" and/or TLS_CACERTDIR in /etc/ldap/ldap.conf directives is where you start.
Less likely causes include:
- inability to check CRLs (check ldap.conf to see if it's enabled)
And assuming nothing else has changed, improbable causes included for completeness:
- server protocol version or cipher set unsupported by client
- change in supported SASL mechanisms