pam_krb5: Error Guessing Name of Local Host Principal
Creating a DNS A record and PTR record for the server that was showing this error resolved the issue.
Alternately, add
[appdefaults]
validate = false
to /etc/krb5.conf (credit: http://www.linuxforums.org/forum/red-hat-fedora-linux/183923-rhel5-6-issues-ldap-krb5-authentication.html#post877263)