We got the authentication failed issue because the windows profile for users used the " "logon workstations" feature and the AD Domian Controller was not listed.
It seems that the Domain Controller needs to be the "trusted broker". After Domino establishes the users Distinguished Nmae in AD using the account credentials stored in Directory Assistance it then "unbinds" and rebinds using the users name and password to see if the password is correct.
If the user profile prevents them accessing the domain controller then the authentication fails.