Pouco depois de postar essa pergunta, eu mesmo encontrei a resposta.
O problema foi que meu ldap_search_base
tinha o usuário de ligação cn=postfix
em /etc/saslauthd.conf
. Depois de alterar a base de pesquisa para a UO Usuários, ela começou a funcionar:)