Acredito que você esteja usando as credenciais de administrador incorretas.
Em vez disso, o Ubuntu é configurado para usar o root em SASL / EXTERNAL Unix Sockets como rootDN por padrão.
# {0}config, config
dn: olcDatabase={0}config,cn=config
olcRootDN: gidNumber=0+uidNumber=0,cn=peercred,cn=external,cn=auth'
Tente usar sudo ldapsearch -H ldapi:/// -Y external -b cn=config