How to re-join an AD2003 domain with Samba after deleting the machine account?

During some troubleshooting I deleted the machine account for a Linux server running samba from our AD 2003 domain. We are using Kerberos for authentication, and after I deleted the machine account I tried to join the domain again using

net ads join -U Administrator

But I keep getting Kerberos errors like these:

[2009/08/18 16:14:36, 0] libads/kerberos.c:ads_kinit_password(228)
     kerberos_kinit_password [email protected] failed: Client not found in Kerberos database
 Failed to join domain: Improperly formed account name

It appears as if samba remembers that it once had an account with the AD and keeps trying to reconnect to it, but I want to create a new account from scratch. I tried to delete all the .tdb files I could find as well as everything under /var/cache/samba but to no avail - it still behaves the same.

I also tried to create the machine account on the AD side, but then I get a similar error when I try to join, about failure to authenticate with the machine account - it looks like samba tries the previous machine account password and I don't know how to reset it, or even if I could figure out what samba uses - how to set it in the AD.

Any help would be greatly appreciated, as at this point the only thing I can think about is to reformat and reinstall the machine, and I would really REALLY love to not do that.

Thanks in advance.

First run a kdestory to remove any reference to the machine account in the local kerberos cache, then manually run kinit [email protected] and enter the password.

Then run the net ads join command.

This should give you the kerberos trust to create the machine account without having to try and use the old machine account credentials.