I would compare the LDAP attributes between a problem machine and a
working machine.Each machine has to have a unique unix account name
and SID.
Normally you don't need to precreate the samba acct with smbpasswd -a
-m or pdbedit. However it may help with the diagnostics to see
what
I found that Samba 3.5.x has trouble creating the LDAP attributes
correctly on new machine accounts . I think Samba 3.4.x was OK.
Rejoining a machine to a domain was usually OK. You need may need to
do a mix of account creation with smbpasswd and LDAP modification with
the LDAP editor.