OK, we have success!
Steps to resolve:
On the DC I was having issues with at the main site, I stopped the KDC Service (Kerberos Key Distribution Center Service)
Then I ran this:
NETDOM RESETPWD /Server: <Domain Controller Name> /UserD:<Domain Admin Username> /PasswordD:<Domain Admin Password>
Rebooted the server.
After this, all of the strange event viewer errors in the DNS log, AD log, etc were gone. I can now successfully replicate across sites as well as join PCs to the domain. I'm not sure why this happened in the first place, but this fixed it.
Thanks for all the help!