This applies to Dell but may also apply to other manufacturers as well. We ran across a few machines that just dropped recently it trust relationship with the server. After doing the basic removing and joining the domain again, it changed to No logon server is available.
First, let me say you need to check the basic issues. DNS entries, IP, Time of domain versus Workstations and such. But if you're in the same case as we were, it won't do you much good.
We found a Dell packaged software application that randomly tosses the workstation off the domain and then when added back on, states there are no logon servers available. If you try to ping and even navigate to the shares of your folders, you will still not be able to login with AD credentials.
This happens because of a Dell released software package called Dell Data Protection Security Tools Authentication Service that turned out to be the cause of our problem. We discovered this by rebooting into safe mode with networking, after hours of troubleshooting the domain and workstation and even attempting a workstation restore that failed.
So one by one, we began to add services and finally were able to determine that the root cause of this was the software package from Dell.
So if you run across this problem and have performed the basic IT checks, look for this service and disable it or contact Dell to see how to configure it differently. I have not seen this on HP yet or other machines that have security software but as technology gets more advanced to secure machines I am sure this will not be the only product that will create these issues.
Editor comment: Note that a Dell KB Article about the removal of this software if deemed necessary, along with links to additional support is available at this link.