DNS isn't always the cause of "selected objects in the following domains are not available"
So if you hit up the 'goog, bing'd it, and everyone that asks about this error:
The Active Directory Domain Controllers required to find the selected objects in the following domains are not available:
contoso.com
Ensure the AD Domain Controllers are available and try to select the object again
...gets told that it's their DNS. But if you're here, I assume you have checked and you don't have a DNS issue. It actually could be your security settings. This error happens when you try and add a user from the trusted domain to a security group in the trusting domain.
Most of the time this happens to people with a one-way trust. (For instance setting up an ESAE, Tier 0 forest, or "red forest"). And sure... DNS could cause this, but I have seen too many forums with people walking away without an answer. In fact the moderators of those forums will see the question, say it is DNS, then mark their own answers as final without confirming with the person who asked, and close the question. It is frustrating.
Here's the other thing that will cause this. The GPO setting:
Computer Configuration > Administrative Templates > System > RemoteProcedure Call > "Enable RPC Endpoint Mapper Client Authentication"
When set to enabled (which is a STIG finding that will soon be removed from 2008R2 and 2012+) it tells the computer account that any RPC communication must be mutually authenticated. Which... is sort of a problem when you only have a one-way trust. You can't just turn this to "Not configured" either, as the setting is tattoo'd. You have to disable it. Then, you have to reboot.
As a bit of trivia, if you had created a one-way trust that was external this wouldn't have happened. In fact, something much more bizarre will (I plan to write a blog about this as well). You can create the trust, add users, and even log on with them. But when logged on with an account from the trusting forest, you will have a frozen start menu. Administrators can't run things as administrator. PsGetSid will tell you that you have a broken trust when clearly you don't.
Strange stuff. Two issues with the same root cause. Hope this helps someone out there.