Eu encontrei o problema. Um dos guias que encontrei no Google me instruiu a fazer
apt-get libnss-ldap libpam-ldap nslcd
Mais tarde, também encontrei um artigo que dizia que libpam-ldapd é mais recente que libpam-ldap e instalou isso.
libnss-ldap solicita algumas configurações e cria um arquivo /etc/libnss-ldap.conf . Então libpam-ldap desinstala libnss-ldap mas deixa seu arquivo de configuração para trás. Aparentemente, esse arquivo de configuração ainda é significativo porque é esse que está usando e eu tive um erro no binddn nesse arquivo. Depois de consertar o binddn, funcionou.
Eu realmente não sei por que você instalaria os dois módulos do ldap. Depois de obter a primeira VM cliente trabalhando, eu configurei outra VM cliente usando apenas libpam-ldapd e nslcd e ela funcionou pela primeira vez.