Se você removeu tudo de /var/lib/ldap/ , você não verá o arquivo DB_CONFIG , o que é necessário para que o slapd (e as ferramentas) saiba quais configurações devem ser definidas para bdb / hdb bases de dados.
Tente executar slapd com a depuração ativada para investigar o que está causando slapd a recusar a inicialização:
# slapd -u ldap -g ldap -d 255
Isso permitirá um registro de depuração muito detalhado em stderr (você terá que ajustar o nome do usuário e do grupo apropriadamente, é claro).