Unable to join Active Directory domain due to inability to set password for computer account

Issue

When attempting to join a RHEL server to an Active Directory domain, we receive an error that the password for the computer account could not be set:

# adcli join example.com -U Administrator@EXAMPLE.COM
 ...
 * Found computer account for <HostName>$ at: CN=<HostName>,OU=Servers,DC=example,DC=com
 ! Couldn't set password for computer account: <HostName>$: Cannot contact any KDC for requested realm
adcli: joining domain example.com failed: Couldn't set password for computer account: <HostName>$: Cannot contact any KDC for requested real