Kerberos authentication not working and results in error "Client not found in Network Authentication Service database or client locked out"

Issue

Kerberos is installed in to allow ssh from one box to the other without having to enter the password. There are a mix of AIX and Red Hat Enterprsie Linux OS's in the enviroment.

KDC logs shows following error:

Feb 17 17:04:34 srv-reg-aix-03 /usr/krb5/sbin/krb5kdc[46764](Notice): AS_REQ (7 etypes {16 1 11 10 15 12 13}) 172.20.1.173(88):
NEEDED_PREAUTH: root/admin@example.com for krbtgt/example.com@example.com, Additional pre-authentication required

Feb 17 17:04:37 srv-reg-aix-03 /usr/krb5/sbin/krb5kdc[46764](info): AS_REQ (7 etypes {16 1 11 10 15 12 13}) 172.20.1.173(88): 
ISSUE: authtime 1266426277, etypes {rep=16 tkt=16 ses=16}, root/admin@example.com for krbtgt/example.com@example.com