Unable to join Red Hat Enterprise Linux 3 and 4 to Windows 2008 R2 with "net ads join".

Issue

Unable to join RHEL machine to Windows domain after upgrading domain server to Windows 2008 R2.

In RHEL 4 machine error is -

# net ads join -U admcwong@EXAMPLE.COM
admcwong@EXAMPLE.COM's password:
Using short domain name -- EXAMPLE
Failed to set servicePrincipalNames. Please ensure that
the DNS domain of this server matches the AD domain,
Or rejoin with using Domain Admin credentials.
Deleted account for 'SYSTEM1' in realm 'EXAMPLE.COM'
Failed to join domain: Type or value exists