Ldap – Cannot connect to Azure AD Domains Service LDAPS using ldapsearch

I'm having some issues trying to connect to ldapsearch to azure ad domains service. From various SO links and how-to's, we've found some commands to try, but none seem to be working.

The bind/base DNs that we're using are apparently correct according to most of the questions on SO and the likes, but I think not!

The command I'm running is this:

ldapsearch -H "ldaps://aaddc.domain.com:636" -Z -d 5 -D "gitlab.ldaps@domain.com" -b "dc=domain,dc=com" -w $password -s sub -x 

Judging by the errors below, it seems like it can connect to the directory, and try to auth, but I think we've got some issues with the dn's that it's trying to bind to, so can't finish the auth. If anyone can shed some light, that'd be amazing.

ldap_url_parse_ext(ldaps://aaddc.domain.com:636)
ldap_create
ldap_url_parse_ext(ldaps://aaddc.domain.com:636/??base)
ldap_extended_operation_s
ldap_extended_operation
ldap_send_initial_request
ldap_new_connection 1 1 0
ldap_int_open_connection
ldap_connect_to_host: TCP aaddc.domain.com:636
ldap_new_socket: 3
ldap_prepare_socket: 3
ldap_connect_to_host: Trying ip_address:636
ldap_pvt_connect: fd: 3 tm: -1 async: 0
attempting to connect: 
connect success
ldap_open_defconn: successful
ldap_send_server_request
ber_scanf fmt ({it) ber:
ber_scanf fmt ({) ber:
ber_flush2: 31 bytes to sd 3
ldap_result ld 0x564972601dc0 msgid 1
wait4msg ld 0x564972601dc0 msgid 1 (infinite timeout)
wait4msg continue ld 0x564972601dc0 msgid 1 all 1
** ld 0x564972601dc0 Connections:
* host: aaddc.domain.com  port: 636  (default)
  refcnt: 2  status: Connected
  last used: Fri Nov  3 13:35:56 2017


** ld 0x564972601dc0 Outstanding Requests:
 * msgid 1,  origid 1, status InProgress
   outstanding referrals 0, parent count 0
  ld 0x564972601dc0 request count 1 (abandoned 0)
** ld 0x564972601dc0 Response Queue:
   Empty
  ld 0x564972601dc0 response count 0
ldap_chkResponseList ld 0x564972601dc0 msgid 1 all 1
ldap_chkResponseList returns ld 0x564972601dc0 NULL
ldap_int_select
read1msg: ld 0x564972601dc0 msgid 1 all 1
ber_get_next
ber_get_next: tag 0x30 len 127 contents:
read1msg: ld 0x564972601dc0 msgid 1 message type extended-result
ber_scanf fmt ({eAA) ber:
read1msg: ld 0x564972601dc0 0 new referrals
read1msg:  mark request completed, ld 0x564972601dc0 msgid 1
request done: ld 0x564972601dc0 msgid 1
res_errno: 1, res_error: , res_matched: 
ldap_free_request (origid 1, msgid 1)
ldap_parse_extended_result
ber_scanf fmt ({eAA) ber:
ber_scanf fmt (a) ber:
ldap_parse_result
ber_scanf fmt ({iAA) ber:
ber_scanf fmt (x) ber:
ber_scanf fmt (}) ber:
ldap_msgfree
ldap_err2string
ldap_start_tls: Operations error (1)
    additional info: 00000000: LdapErr: DSID-0C090FF6, comment: TLS or SSL already in effect, data 0, v2580
ldap_sasl_bind
ldap_send_initial_request
ldap_send_server_request
ber_scanf fmt ({it) ber:
ber_scanf fmt ({i) ber:
ber_flush2: 48 bytes to sd 3
ldap_result ld 0x564972601dc0 msgid 2
wait4msg ld 0x564972601dc0 msgid 2 (infinite timeout)
wait4msg continue ld 0x564972601dc0 msgid 2 all 1
** ld 0x564972601dc0 Connections:
* host: aaddc.domain.com  port: 636  (default)
  refcnt: 2  status: Connected
  last used: Fri Nov  3 13:35:56 2017


** ld 0x564972601dc0 Outstanding Requests:
 * msgid 2,  origid 2, status InProgress
   outstanding referrals 0, parent count 0
  ld 0x564972601dc0 request count 1 (abandoned 0)
** ld 0x564972601dc0 Response Queue:
   Empty
  ld 0x564972601dc0 response count 0
ldap_chkResponseList ld 0x564972601dc0 msgid 2 all 1
ldap_chkResponseList returns ld 0x564972601dc0 NULL
ldap_int_select
read1msg: ld 0x564972601dc0 msgid 2 all 1
ber_get_next
ber_get_next: tag 0x30 len 104 contents:
read1msg: ld 0x564972601dc0 msgid 2 message type bind
ber_scanf fmt ({eAA) ber:
read1msg: ld 0x564972601dc0 0 new referrals
read1msg:  mark request completed, ld 0x564972601dc0 msgid 2
request done: ld 0x564972601dc0 msgid 2
res_errno: 49, res_error: , res_matched: 
ldap_free_request (origid 2, msgid 2)
ldap_parse_result
ber_scanf fmt ({iAA) ber:
ber_scanf fmt (}) ber:
ldap_msgfree
ldap_err2string
ldap_bind: Invalid credentials (49)
    additional info: 80090308: LdapErr: DSID-0C09042F, comment: AcceptSecurityContext error, data 52e, v2580
ldap_free_connection 1 1
ldap_send_unbind
ber_flush2: 7 bytes to sd 3
ldap_free_connection: actually freed