Samba: ads_connect: No logon servers

[ATC]

Trying to connect Samba 3.0.28 to a Windows 2003 AD domain, the same error message keeps popping up everywhere. DNS, Winbind and Kerberos appear to be properly configured, but Samba still can't find the logon server.

$ net ads join -UAdministrator
Administrator's password:
[2009/04/21 17:38:27, 0] utils/net_ads.c:ads_startup_int(286)
  ads_connect: No logon servers
Failed to join domain: No logon servers

$ net ads status
[2009/04/22 17:20:35, 0] utils/net_ads.c:ads_startup_int(286)
  ads_connect: No logon servers
[2009/04/22 17:20:37, 0] utils/net_ads.c:ads_startup_int(286)
  ads_connect: No logon servers

[ATC]

According to the documentation at samba.org the following entry in smb.conf is unnecessary:

password server = 10.0.0.10

Interestingly, using the hostname, domain name and pretty much anything else pointing to the exact same host achieved nothing, but using the IP address of the PDC made everything work.