It turns out our primary active directory domain controller had died. I don't really have any experience with setting up AD servers so needed a little help with this. Luckily this was quite useful: Installing an Additional Domain Controller by Using the Graphical User Interface (GUI).
So, I started doing this, but then ran into a problem when running the Active Directory Domain Services Installation Wizard (dcpromo.exe): You will not be able to install a writable replica domain controller at this time because the RID master [my primary DC] is offline.
After clicking on No, the following popup was displayed: The transfer of the operations master role cannot be performed because: The requested FSM operation failed. The current FSMO holder could not be contacted.
Well, duh! As I was saying, the primary DC is down. Doing some more searching I found this: Seizing FSMO Roles.
So, I went back to my old backup DC, seized all FSMO roles, then made my new box the new backup DC as I originally started out doing. Now everything is okay again. I just have to update all my DNS search settings since the new box has a different IP address.