I used to have this issues with one of my DCs. I had two in that site. For any reason when I restarted one, I noticed that the other couldn't authenticate users. I removed its role as a GC, restarted, put the role back. It fixed. I don't know what will happen in your case if you don't have other DCs in other sites, if you have any.