The issue was not that the cert was not accepted but the fact the certs DNS/SAN was not set to the URL I was using. One out of 8 thus the intermittent issue.
What I did was get the IP list of the ldap_url then ran this command on every LDAP IP
echo -n | openssl s_client -connect 10.56.100.47:636 | openssl x509 -noout -text | grep DNS:
The output then showed one was missing the ldap_url. All certs were valid and signed, just not for the ldap_url being used.