> Должны быть DNS записи как в пункте "Пример регистрации имен" вот этой
> статьи http://itband.ru/2010/03/active-directory-works-with-dns/. По ним и происходит
> поиск служб Active Directory.

Насколько смог, разобрался в дереве DNS Manager на виндовом сервере - эти четыре записи из статьи у меня есть.

Запросил dig:
#dig -t srv _ldap._tcp.mydomain.ru _kerberos._tcp.mydomain.ru _ldap._tcp.dc._msdcs.mydomain.ru _kerberos._tcp.dc._msdcs.mydomain.ru

Вот его вывод, только мусор вырезал:

;; QUESTION SECTION:
;_ldap._tcp.mydomain.ru.              IN      SRV
;; ANSWER SECTION:
_ldap._tcp.mydomain.ru.       600     IN      SRV     0 100 389 ad2.mydomain.ru.
_ldap._tcp.mydomain.ru.       600     IN      SRV     0 100 389 ad1.mydomain.ru.

;; QUESTION SECTION:
;_kerberos._tcp.mydomain.ru.          IN      SRV
;; ANSWER SECTION:
_kerberos._tcp.mydomain.ru.   600     IN      SRV     0 100 88 ad2.mydomain.ru.
_kerberos._tcp.mydomain.ru.   600     IN      SRV     0 100 88 ad1.mydomain.ru.

;; QUESTION SECTION:
;_ldap._tcp.dc._msdcs.mydomain.ru.    IN      SRV
;; ANSWER SECTION:
_ldap._tcp.dc._msdcs.mydomain.ru. 600 IN      SRV     0 100 389 ad1.mydomain.ru.
_ldap._tcp.dc._msdcs.mydomain.ru. 600 IN      SRV     0 100 389 ad2.mydomain.ru.

;; QUESTION SECTION:
;_kerberos._tcp.dc._msdcs.mydomain.ru.        IN      SRV
;; ANSWER SECTION:
_kerberos._tcp.dc._msdcs.mydomain.ru. 600 IN  SRV     0 100 88 ad1.mydomain.ru.
_kerberos._tcp.dc._msdcs.mydomain.ru. 600 IN  SRV     0 100 88 ad2.mydomain.ru.

;; ADDITIONAL SECTION:
ad1.mydomain.ru.             3600    IN      A       192.168.1.2
ad2.mydomain.ru.             3600    IN      A       192.168.1.3

Где ещё покопаться?