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:)