What order did you build (or rebuild) the certificates and/or servers in? It is possible that you have an error with the Certificate Authority (CA) certificates like I have.
I have a MTA server, and a LDAP/MAILSTORE server. I had to rebuild the certs on the MAILSTORE, which included the CA certs. But because the MTA has the old root certificate, I am now getting that error. I know I have to replace it on the MTA and re-sign the server certificate. However, all of the documentation I have found is mailstore based. Everything wants me to recreate a new CA on the MTA and install it.
I do see where you can make sure that, at least, the LDAP has the correct information.
From the SSL Certificate documentation you have already linked to:
* To update CA cert stored in LDAP (as zimbra):
zmprov -l mcf zimbraCertAuthorityKeySelfSigned "`cat /opt/zimbra/ssl/ssl/ca/ca.key`"
zmprov -l mcf zimbraCertAuthorityCertSelfSigned "`cat /opt/zimbra/ssl/ssl/ca/ca.pem`"
* You can see your updated certs in LDAP now and compare them to contents of /opt/zimbra/ssl/ssl/ca (as zimbra)
zmprov -l gcf zimbraCertAuthorityKeySelfSigned
zmprov -l gcf zimbraCertAuthorityCertSelfSigned
You should do those last two commands on both machines. That way you can see if your problem is the Cert Authority
If not, then we have more information to help you track down your problem.