NTLM Authenticated LDAP Queries

I ran netdiag with the -v verbose option from a client and it returns LDAP errors when trying to do NTLM Authenticated LDAP Queries against either of my domain controllers. non-authenticated queries work ok, only the NTLM queries fail. The log file shows as follows

Do NTLM authenticated LDAP call to 'dc.foolocal'
[FATAL] Cannot do NTLM authenticated ldap_bind to 'dc.foo.local': Invalid Credentials

Do Negotiate authenticated LDAP call to 'dc.foo.local'
[FATAL] Cannot do Negotiate authenticated ldap_bind to 'dc.foo.local': Invalid Credentials

I am running the netdiag utility while logged in with a domain admin user account. I can't find anything on microsoft.com or the newsgroups or google regarding that error message. Has anyone run into this?