I would try to bind using Directory Utility and it kept failing on step 3. I turned on DirectoryService debugging with the handy command-y:
sudo killall -USR1 DirectoryService
That produced some cool errors such as:
Active Directory: Password verify for rzm102@DOMAIN.COM failed with error -1765328230
Plug-in call "dsDoPlugInCustomCall()" failed with error = -14090.
Let me just say, I know my password. I didn't forget it. I type it in my machine hundreds of times a day, so it's not that!
What it was, was very interesting. I found this thread that lead me to the real issue. Apparently, the /var/db/dslocal/nodes/Default/config/Kerberos\:AD.DOMAIN.NAME file had become corrupted. When I went to cat the file, it displayed with some funky text, not the plist I was expecting.
Removing this file allows rebinding and fixes the issue. Yay!