RHEL 6: Winbind error in Samba logs: 'kinit succeeded but ads_sasl_spnego_krb5_bind failed: Cannot find KDC for requested realm'.

Issue

• Getting error as: "winbindd[28673]: kinit succeeded but ads_sasl_spnego_krb5_bind failed: Cannot find KDC for requested realm."
• Following winbind errors are seen in logs files - in /var/log/messages:

Apr 30 15:37:55 hostname winbindd[28673]: [2013/04/30 15:37:55.577178,  0] libads/sasl.c:908(ads_sasl_spnego_bind)
Apr 30 15:37:55 hostname winbindd[28673]:   kinit succeeded but ads_sasl_spnego_krb5_bind failed: Cannot find KDC for requested realm

And in /var/log/samba/log.wb:

[2013/04/30 15:37:55.556239,  1] libsmb/clikrb5.c:710(ads_krb5_mk_req)
  ads_krb5_mk_req: smb_krb5_get_credentials failed for ldap/hostname.ad.example.com@AD.EXAMPLE.COM (Cannot find KDC for requested realm)
[2013/04/30 15:37:55.577101,  1] libsmb/clikrb5.c:710(ads_krb5_mk_req)
  ads_krb5_mk_req: smb_krb5_get_credentials failed for ldap/hostname.ad.example.com@AD.EXAMPLE.COM (Cannot find KDC for requested realm)
[2013/04/30 15:37:55.577178,  0] libads/sasl.c:908(ads_sasl_spnego_bind)
  kinit succeeded but ads_sasl_spnego_krb5_bind failed: Cannot find KDC for requested realm
[2013/04/30 15:37:55.577397,  1] winbindd/winbindd_ads.c:134(ads_cached_connection)
  ads_connect for domain ADROOT failed: Cannot find KDC for requested realm
[2013/04/30 15:38:53.992052,  3] winbindd/winbindd_misc.c:160(winbindd_dual_list_trusted_domains)
  [28670]: list trusted domains
[2013/04/30 15:38:53.992128,  3] winbindd/winbindd_misc.c:167(winbindd_dual_list_trusted_domains)
  winbindd_dual_list_trusted_domains: trusted_domains returned NT_STATUS_UNSUCCESSFUL