I recently started trying to use Ansible to manage all of the disparate systems I have at the office, and in trying to set up Ansible to communicate with our Windows systems, I ran into this (among other) issues. Despite having all of the right ports open to communicate with WinRM, a couple of systems were giving the error
Server not found in Kerberos database
After some digging, I discovered that Kerberos is highly dependent on DNS to be able to perform both a forward and reverse lookup. In my case, my reverse lookup zone had not correctly populated for the servers that were giving this error.