You might come across this error when trying to join a computer to a Windows domain that has had a secondary domain controller promoted through FSMO. The client will give an error stating the domain does not exist. This is the result of a DNS error because the necessary DNS entries were not created (they are normally created when first configuring a primary domain controller).
I found that it is possible to correct this issue by manually adding the DNS entries.
Open up your DNS server configuration on the promoted domain server.
In the pane to the right, right click and select "New other records"
Select "Service Location(SRV)" from the list
Next to Service type "_ldap"
Next to Protocol type "_tcp"
For priority, set it to 0
For Weight, set it to 100
The port number is 389
Under Host offering this service, type "yourserver.your.domain.com"
(where yourserver is your promoted domain controller)
The recently promoted domain server is named PDC02
The domain is internal.contoso.com