Fortunately, our network admin had this handy PowerShell command to run to rectify the issue with no service interruptions whatsoever.
Open PowerShell as administrator. Run this command sequence:
$credential = Get-Credential
A window will pop up, type in a Domain administrator account and password.
Reset-ComputerMachinePassword -Server (Active Directory name).local
Where (Active Directory name) is replaced with the name of your active directory. This required having a local admin account on the system having domain connectivity issues
MSDN has more details on Reset-ComputerMachinePassword.