So today, my Certificate Authority decided it was too good for my Sandbox Domain and wanted to do its own shindig.

Unfortunately, you cannot leave a domain and rejoin it back since it's a CA.  However, before you start backing up your CA and wipping out your Windows Server 2008 R2 disk, give this a shot:

1. Login to the machine as local admin that is presenting the "The trust relationship between this workstation and the primary domain failed" error.

2. Open up a commmand prompt as Administrator

3. Execute the following command: netdom resetpwd /s:nameofyourdcserver /ud:domain\User /pd:*

Hurray!  You should be back in business now without even having to reboot! 🙂

You can find more info about how the tool works behind the scenes from here:http://support.microsoft.com/kb/325850