Windows cannot connect to the domain either because the domain controller is down or otherwise unavailable, or because your computer account was not found.

Hello,

We are having an issue where one computer on the network isn't able to log on to the domain because it gives the error stated in the title of this post.  The DC is a Windows Server 2003 SBS machine, and it's up and running, I even tried restarting the DC and the client machine and the issue still persists. The DHCP on the DC isn't configured and isn't running, so the "DHCP Server" is actually a Linksys router, that's what's handing out IP's.  It's a small environment, only about 5-6 computers, so that's why they have been able to get away with not having the DC be the DHCP server, regardless everything has been working fine, up to now and it's only this one computer.  

Just for reference the computer name of the problem machine is "CARLOS"

When I look at the server event viewer the following event is logged which I think is related to the issue:

"The session setup from the computer CARLOS failed to authenticate. The name(s) of the account(s) referenced in the security database is CARLOS$.  The following error occurred:
Access is denied. "

Then the following error is logged right after:

"The kerberos client received a KRB_AP_ERR_MODIFIED error from the server CARLOS$.  The target name used was cifs/CARLOS. This indicates that the password used to encrypt the kerberos service ticket is different than that on the target server. Commonly, this is due to identically named  machine accounts in the target realm (PROLOCKANDSAFE.LOCAL), and the client realm.   Please contact your system administrator."

I've looked around the internet for solutions to this problem and I've already verified the time on the client computer and time on the server are identical or no more than 5 minutes apart, and they are actually one minute apart which shouldn't be causing the issue.  I've also looked at the DNS and made sure that there aren't duplicate A Record's using the same IP address that this problem computer is using, and there isn't.  I've tried running WinSock XP 1.2, but that didn't work either.  

The only thing I haven't tried doing is removing the computer from the domain, deleting the computer account from AD, renaming the computer and rejoining it to the domain.  It seems according to the articles I've read that this is the way to really fix it, but I'm weary about removing the computer from the domain in case I encounter another error when trying to rejoin the computer.

Any help or advice would be greatly appreciated, thank you!