Every time the TDM Portal Service is restarted, the first AD authentication attempt always fails. Once the connection is established the problem is not seen, until the TDM Portal service is restarted,
TDM 4.9.1+
The problem was caused by the "Referral Strategy" configuration used in the AD/LDAP configuration for TDM Portal. The Referral Strategy specifies whether you want to Follow or Ignore the reference to another source if the user in one group is also a part of the other group. Select the respective option from the drop-down list.
Initially the "Referral Strategy" configuration was set to "Ignore":
Changing the "Referral Strategy" to "Follow" resolved the issue.
For more information, see LDAP Integration with the CA TDM Portal