After further investigation, we noticed that the server in question was unable to connect to the Domain Controller, which was causing the problem. What was weird is that this only happened on certain calls to the domain controller. Some calls worked and some didn't. We concluded that it was easier to rebuild the server and start from scratch. With the new server built, we didn't have any issues.
Is this a good answer? Probably not. In this case the server was sick and we euthanized it. Sometimes its easier to start over then spend 3 days trying to figure out the issue (which we did).