Domain Mishap

Backstory:

I was going through our active directory computer list and was removing old entries that I thought did not exist anymore. I ended up deleting a computer that was still active. I have done this in the past and the way i always fixed it was to unjoin the computer from the domain, restart, change the computer name, restart, and rejoin the domain. That always seemed to work. However, this is my first time doing this to a vista computer and it is not working.

I am logged into the computer as the local administrator. I try to join the domain using the domain admin credentials. I get this:

"The following error occured attempting to join the domain "domainname.com ": The network path was not found.

I am getting an IP address via dhcp. I can ping the domain controller by name and by IP. There are no (visible) records of this machine in active directory anywhere.

How do I fix this?

Edit: The machine in question is running Windows Vista Business

 

I used to get this error if I didn't have the DC as primary dns.
You might also want to try creating a new computer acct in AD.