RC's friend here, as you guys know, I got that message while trying to connect to his domain.
We've run DCPROMO several times over.(not to mention reinstalling everything)
First time we tried this we were using one of those free domains they pass out at dyndns and we also forwarded DNS requests to their nameservers(If i recall directly the DNS at one point was directed to localhost, but I don't think that yielded any different result.) After setting up the AD, the DNS and DC needed to run AD, I tried to connect to his domain via the internet, I would receive a similar message as the one I gave above, except it would find the SRV records yet none of them pointed to a domain controller.
After getting the same message over and over, he opted to get a top level domain due to us assuming it had something to do with using a subdomain.
After finding a provider to host the domain, we reinstalled everything, ran DCPROMO and this time forwarded the dns requests to said provider.
Also, to double check, I ran nslookup with the set type=all parameter to check _ldap._tcp.dc._msdcs.horc.me for the SRV records and couldn't find the server, let alone said records.
Funny thing is I cannot ping the server either. I don't know if that's because the server itself is hosted on a virtual machine or what.
As for the DNS IP's you see, the first one is his, the second one is my ISP's. I opted to keep the latter in case his would not forward my request. I've tried with only the server's IP and subsequently lost all ability to connect to any website.