I wonder if this isn't some AD syncronisation issue but I'm pretty sure I didn't see this with 3.0.23c. Issue also existed in 3.0.25.

We have password server = * in our config file but I have also tried setting it to one of our servers with no difference.

Example (note times):

[root@pc ~]# net ads join -U support -W domain
support's password: 
Using short domain name -- domain
Joined 'pc' to realm 'DOMAIN.COM'
[root@pc ~]# date
Wed Sep 26 04:07:13 EDT 2007
[root@pc ~]# net ads testjoin -P
[2007/09/26 04:08:36, 0] libads/kerberos.c:ads_kinit_password(228)
  kerberos_kinit_password pc$@DOMAIN.COM failed: Client not found in Kerberos database
[2007/09/26 04:08:37, 0] libads/kerberos.c:ads_kinit_password(228)
  kerberos_kinit_password pc$@DOMAIN.COM failed: Client not found in Kerberos database
Join to domain is not valid: Improperly formed account name
[root@pc ~]# net ads testjoin -P
[2007/09/26 04:12:29, 0] libads/kerberos.c:ads_kinit_password(228)
  kerberos_kinit_password pc$@DOMAIN.COM failed: Client not found in Kerberos database
[2007/09/26 04:12:30, 0] libads/kerberos.c:ads_kinit_password(228)
  kerberos_kinit_password pc$@DOMAIN.COM failed: Client not found in Kerberos database
Join to domain is not valid: Improperly formed account name
[root@pc ~]# net ads testjoin -P
Join is OK
[root@pc ~]# date
Wed Sep 26 04:23:50 EDT 2007