We've experienced this as well and in our instance it appears to be related to an older domain controller running on an ancient (like brontosaurus times in terms of IT) incarnation of Windows. It seems that whenever the member server boots and selects that old DC as it's logon server, then the problem materializes. Both the old and new DC are fully replicated to one another and so that's not the issue, and it doesn't occur every time which is a bit frustrating.
In any event the test we did was to shutdown that specific older DC, reboot the member server so that it selects a different DC, and then it authenticated just fine. It's still possible that this was not the issue but thus far each time we've experienced this joy, we've performed the same process and the problem went back into it's cave. Obviously upgrading the old DC is on the insanely long backlog of things to do.