Windows – How to determine the values for an LDAP bind to a Windows Server 2012 DC? [Gitlab Omnibus 7.0.0; ldap_bind: Invalid Credentials (49)]

EDIT: This question has gotten a lot of views, and I never really came back and provided a precise, step-by-step solution. So I came back 18 months later and did that. This solution works for simple binds, and the original question is posed in the context of trying to get a Gitlab Omnibus installation to bind to the LDAP server, but it should work in the case of any simple LDAP bind. See my accepted answer for the exact steps I did to produce a solution. Here are my Gitlab version details (for those who have this problem with Gitlab):

• GitLab 7.0.0

• GitLab Shell 1.9.6

• GitLab API v3

• Ruby 2.1.1p76

• Rails 4.1.1

Original Post:
I have been trying for nearly 6 hours to get my Gitlab deployment to authenticate via Windows Server 2012 Essentials Active Directory LDAP.

I am running Ubuntu 14.04 for my Gitlab server. It's already connected to the domain controller via SSSD.

Gitlab itself uses LDAP settings from in the gitlab.rd configuration file like follows:

# These settings are documented in more detail at
# https://gitlab.com/gitlab-org/gitlab-ce/blob/master/config/gitlab.yml.example#L118
gitlab_rails['ldap_enabled'] = true
gitlab_rails['ldap_host'] = 'hostname of LDAP server'
gitlab_rails['ldap_port'] = 389
gitlab_rails['ldap_uid'] = 'sAMAccountName'
gitlab_rails['ldap_method'] = 'plain' # 'ssl' or 'plain'
gitlab_rails['ldap_bind_dn'] = 'CN=query user,CN=Users,DC=mycorp,DC=com'
gitlab_rails['ldap_password'] = 'query user password'
gitlab_rails['ldap_allow_username_or_email_login'] = true
gitlab_rails['ldap_base'] = 'DC=mycorp,DC=com'

I am able to query the server, but no matter what settings I choose, I ALWAYS get the same message:

"Invalid Credentials"

I have tried to manually query the DC using ldapsearch and the same error message:

"ldap_bind: invalid credentials (49)

I already created the user I am using to bind on the Active Directory Users section in my Windows Server 2012 Server Manager.

I have tried every single combination of OU=Users, and CN=Users and other users, made sure that all the email address fields for all users in the AD are populated, but I cannot get a single proper response.

Isn't there an easy way to return all the Bind_dn and Base information for an Active Directory object? This is getting very frustrating.

No matter where I look on the internet, all the information pertains to old versions of Windows (ldapsearch, etc…). I am very new at this Systems stuff (this is at my very first summer internship job).

Here is an example of the current settings I am using:

gitlab_rails['ldap_bind_dn'] = 'CN=Gitlab LDAP,OU=Users,DC=servername,DC=local'
gitlab_rails['ldap_base'] = 'OU=Users,DC=servername,DC=local'

And a corresponding example of how I've been trying to use ldapsearch to find the proper bind settings for my Windows AD DS:

ldapsearch -b "ou=Users,dc=servername,dc=local" -h 192.168.0.3 -p 389 -D "uid=Gitlab LDAP,ou=Users,dc=servername,dc=local" -w "<password>"

To no avail. I've tried dozens of combinations. The user "gitlab" has a display name of "Gitlab LDAP" in the Windows Server, with an email, all in lower-case. Bottom line: Is there some easy way to click on object in the Windows DC and retrieve the correct LDAP settings to use that user object for ldap binds?! If I were prone to emotional outbursts, this is where I would do it.

Always the same error message:
"Invalid Credentials"

Thank you for your time and consideration, any and all help will be greatly appreciated.