[Samba] _netr_ServerAuthenticate3: netlogon_creds_server_check failed. Rejecting auth request

[Paul Tietjens]

I am getting errors in my samba logs like "_netr_ServerAuthenticate3:
netlogon_creds_server_check failed. Rejecting auth request from client
XXX machine account XXX$" (Host log: http://pastebin.com/QXhbngN5).

So far, machines do seem to join the domain (Machine account is
created in LDAP, user can log in, etc), but I am concerned that when
Windows 7 machines reach their 30 days they will begin issuing "trust
account has expired or is incorrect" messages.

Since we have a couple thousand machines, I wish to avoid that.  I
have followed the instructions at
http://wiki.samba.org/index.php/Windows7 and tried a few other thnigs
(but have not touch the sign/seal regkeys) and still get these errors
in the logs when a machine boots and auths any user.  I have updated
the samba bins from debian backports to run version  3.5.8.

I have made sure that our DNS server registers the machine account
with hostname.DOMAIN, have tried turning off/on ntlmv2 on the server
and using gpedit on the client, have made sure that time is
synchronous on the server/client, have removed and re-added the
machine account many times, and have tried some registry hacks like:
HKLM\System\CCS\Services\TcpIp\Parameters
Domain: XXX.com
NV Domain: XXX.com

Where should I look next?