Missing DNS SRV record "_ldap._tcp.dc.domainname
I searched for it in DNS and even ran an NSLOOKUP....which lead me to my discovery....
My NSLOOKUP was defaulting to a server called "::1". After changing it in the command line I noticed I was able to find the SRV record. As it turns out IPv6 is enabled and set to "automatically obtain address". This causes the primary client DNS to be "::1" if you don't have IPv6 set up in your network.
By unchecking IPv6 in the network properties the IPv4 DNS IP's took affect and POW!!! It worked.
I chased this one down and ran in circles for a while before figuring it out. :S