When this error message pops up, users are unable to sign-in to their devices in the domain. “We can’t sign you with this credential because your domain isn’t available. Make sure your device is connected to your organization’s network and try again. If you previously signed in on this device with another credential, you can sign in with that credential”.
Note: This is is a DNS issue and all your troubleshooting tips should be centred on it. Others sites also reference policy issue but this was not so for me.
Note: I was still able to sign-in to this device with other cached credentials. But was not able to sign-in with newly created user account. Until these errors were fixed, I was not able to sign-in with new credentials (user account and password).
Below were the following errors I had and upon fixing these errors, I was able to log-on to these devices with the newly created credentials. PLEASE work through the errors below and apply the needed fix for your environment.
1: Ensure the DNS server has the right IP address of itself populated for all zones and records. A similar idea was used in resolving this issue “How to fix nslookup unknown: cannot find non-existent domain“.
2: The following errors occurred attempting to join the domain: The specified domain either does not exist or could not be contacted
3: The following error occurred when DNS was queried for the service location (SRV) resource record used to locate an Active Directory Domain Controller (AD DS) for domain: Error code 0x0000232B RCODE_NAME_ERROR.
For other possible errors, see the following link. They were not applicable to me but might be of help to you.