So, your computers domain account has gone bad. And you know that the way to fix this is to leave the domain and rejoin. Well don’t.

Here is how you ca fix this with one command + one reboot:
Command:
netdom.exe resetpwd /s: /ud: /pd:*

Then Reboot.

If your machine is a domain controller then here is how you fix this:

Turn off the Kerberos Key Distribution Center service. You can do this in the Services MMC snap-in. Set the startup type to Manual. Reboot.
Remove the Kerberos ticket cache. A reboot will do this for you, or you can remove them using KerbTray.exe. You can get that tool here: http://www.microsoft.com/download/en/details.aspx?displaylang=en&id=17657
Post change steps. Do these in conjunction with 5 below. Turn the Kerberos Key Distribution Center Service back on before rebooting. You should reboot the domain controller and then force replication in the Active Directory Sites and Services MMC snap-in.
Run netdom.exe to change the password.
Open an administrative command prompt. On Windows platforms with UAC enabled, you will need to right-click on cmd.exe and select “run as Administrator”.
Type the following command: netdom.exe resetpwd /s: /ud: /pd:*
Reboot the machine.

Source and a great Blog.
http://implbits.com/About/Blog/tabid/78/post/don-t-rejoin-to-fix-the-trust-relationship-between-this-workstation-and-the-primary-domain-failed/Default.aspx