rhevm-manage-domains fails to join domain, 'Error: Authentication Failed' or 'Error: LDAP query Failed.'

Issue

Trying to add an Active Directory domain using rhevm-manage-domains encounters either of the following errors:

# rhevm-manage-domains -action=add -domain=rhev.example.com -user=rhevadmin -password=xxxxx
Error: Authentication Failed. Please verify the fully qualified domain name that is used for authentication is correct.. Problematic domain is: rhev.example.com
Failure while applying Kerberos configuration. Details: Authentication Failed. Please verify the fully qualified domain name that is used for authentication is correct.

OR

# rhevm-manage-domains -action=add -domain=rhev.example.com -user=rhevadmin -password=xxxxx
javax.naming.AuthenticationException: GSSAPI [Root exception is javax.security.sasl.SaslException: GSS initiate failed [Caused by GSSException: No valid credentials provided (Mechanism level: Server not found in Kerberos database (7))]]
        at com.sun.jndi.ldap.sasl.LdapSasl.saslBind(LdapSasl.java:150)
        at com.sun.jndi.ldap.LdapClient.authenticate(LdapClient.java:212)
...
Error: LDAP query Failed. Error in DNS configuration. Please verify the RHEV Manager host has a valid reverse DNS (PTR) record.
Failure while testing domain rhev.example.com. Details: No user information was found for user