AD users not able to login with Error : "Kinit failed: Cannot find KDC for requested realm"

Issue

AD users not able to login with Error : "Kinit failed: Cannot find KDC for requested realm"

Following errors are seen in /var/log/samba/log.wb-EXAMPLE

[2015/05/31 09:08:09.712286,  0] libsmb/cliconnect.c:1865(cli_session_setup_spnego)
   Kinit failed: Cannot find KDC for requested realm
 Jun  3 10:12:46 sfodv-ora03 sshd[2508]: pam_succeed_if(sshd:auth): error retrieving information about user measbox
 Jun  3 10:12:47 sfodv-ora03 sshd[2508]: Failed password for invalid user measbox from 10.221.66.62 port 53141 ssh2