This is a remainder of the well-known (and documented) error that comes up with
using a Samba-Domain-Controller in a replicated OpenLDAP-Setup:

If you join a workstation onto a Domain-Controller that itself is configured to
use a readonly OpenLDAP-Slave the account is not replicated fast enough. Thus
the modified or created account will not be found by the subsequent
pdb-functions and your domain join will fail. 

The problem is very easy to workaround with simple sleep-calls in
passdb/passdb.c:local_password_change and/or source/rpc_server/srv_samr_nt.c
(don't remember where exactly)

Andrew Bartlett proposed to invent sequence-number(s) to track replicated entries.