I'd also tried ldapsearch.
The syntax which I used was:
ldapsearch -h mydomain.com -b "cn=test user,dc=mydomain,dc=com" -w
It returns ldap bind error.
- First of all, it's great that you tried ldapsearch, isolating it to an LDAP usage problem (and taking DA out of the picture).
I don't remember if you need to authenticate to AD. In any case use the -D and -w switches to supply the userdn and password. I don't know if your -b was a typo when you meant to use -D. For help on the options, run ldapsearch without any arguments.
Normal Active Directory naming likes to place users in a hierarchy like "cn=test user,cn=users,cn=mymachine,dc=mydomain,dc=com". Make sure you've got the naming correct.