Infelizmente, você não forneceu detalhes suficientes. A outra parte infeliz é que não tenho familiaridade suficiente com o AIX para saber quais utilitários ou o que é usado em um sistema AIX. Vou dar exemplos baseados no Linux.
Quando você recebe ldap_start_tls_s(): Can't contact LDAP server erros, isso geralmente é um indicador de um certificado de CA ausente ou configuração defeituosa. Você precisa garantir que seu ldap.conf (seja o /etc/ldap.conf, /etc/sudo-ldap.conf, etc) esteja configurado corretamente. Aqui está um exemplo da configuração correta no Linux.
uri ldap://ldap.example.com
ssl start_tls
tls_cacertdir /etc/openldap/cacerts
tls_cacertfile /etc/openldap/cacerts/cacert.pem
sudoers_base ou=SUDOers,dc=example,dc=com
Este é o mínimo que você pode se dar bem. O fato é que provavelmente você está perdendo um certificado CA, ou houve mudanças nos certificados ou CAs para os certificados do servidor LDAP. Você precisa resolver isso.
A outra coisa é, se sua configuração estiver correta e seus certificados estiverem corretos, você também pode precisar de um link simbólico com hash do certificado de CA. Isto é especialmente o caso quando se utiliza utilitários openldap.
ln -s cacert.pem 'openssl x509 -hash -in ca.pem -noout'.0