I was finally able to solve this problem. I did a secedit dump on my "broken" domain controller and noticed these entries:
These entries come from a user rights policy that is applied to all servers (non-DC) in our domain. It seems these policies are sticky though. Since once the policy is not applied, they are not reverted. To fix this, I created a new policy that does define one of the groups I still want in the policy, "DenyLogonLocally". Once this policy was applied it overwrote the other settings, and I am now able to login. I imagine I could have updated the secedit policy manually but I wanted something in place for future server promotions, so I don't have this headache again.
I hope this helps someone. Deny's are the worst!