Сначала быстрое решение:
Добавить следующую строку в файл /etc/ldap/ldap.conf:

TLS_CIPHER_SUITE  NORMAL:%VERIFY_ALLOW_BROKEN

А теперь немного контекста.
На Ubuntu 20.04 LTS столкнулся проблемой, аналогичной этой.
Т.е. идём клиентом в LDAP (через STARTTLS), корневой сертификат в систему добавлен, но, например, следующая команда:

ldapwhoami -H ldap://domain.com -x -ZZ

говорит "ldap_start_tls: Connect error (-11)"

А следующая команда из пакета gnutls-bin:

gnutls-cli --print-cert --starttls-proto ldap -p 389 domain.com

проверяет цепочку сертификатов и сообщает следующее: "signed using RSA-SHA1 (broken!)",  "- Status: The certificate is NOT trusted."

Методом чтения документации, проб и ошибок, приходим к выводу, что ключевое слово NORMAL включает все секурные на данный момент алгоритмы, а %VERIFY_ALLOW_BROKEN допускает использование алгоритмов MD5 и SHA1 в подписях. Разделяются они двоеточием.
Итоговая команда для теста выглядит так:

gnutls-cli --print-cert --starttls-proto ldap -p 389 --priority NORMAL:%VERIFY_ALLOW_BROKEN domain.com

Ну а параметр конфига для LDAP я уже привёл в самом начале статьи.

Напоследок замечу, что на уровне всей системы эту задачу можно решить с помощью криптополитик.