When a Mac is imaged, the local KDC is imaged together with it. This causes the SHA1 key used in the local KDC to be replicated. When the image is bound to the AD, this would result in the machine being unable to bind due to replicate SHA1 keys. This is reflected at the support pages (http://support.apple.com/kb/TS1245)

To solve this, remove traces of the local KDC and reset it. Using Keychain Access, locate the com.apple.kerberos.kdc certificate and key pair in the System keychain. And delete all three entries. Then do the following commands.

sudo rm -fr /var/db/krb5kdc
sudo /usr/libexec/configureLocalKDC