I have just spent the best part of the last week trying to figure out the following issue. As I suspected, it turned out to be something pretty simple and yet it was nearly impossible to find someone with an answer, so I hope this is useful to someone in a similar situation.
About 6 weeks ago I upgraded one of our customers from a 5 server 2000/2003 setup to 3 servers on 2008. Most of this went fine, including the migration from Exchange 2003 to 2010. The configuration is one site, 2 domains in a parent-child setup. 2 DCs in the parent domain, 1 in the child.
About this time last week we started to have issues with OWA. Users from the child domain couldn't log into webmail and were presented with "A server that contains information about your user account and mailbox can't be found", and then lower down the diagnostics page "Exception message: Could not find any available Domain Controller in domain"
I then started to get reports that users in the parent domain couldn't access resources in the child domain. At this point I checked all the basic DNS resolution and found no issues, so I had a look at the trust - unfortunately as this is a Parent-Child topology there's very little you can do to the trusts in AD Domains and Trusts.
I could still log in to the child domain as parent\administrator and so wasn't convinced that the trust was to blame.
We then started getting replication failures. The 2 Parent DCs could initiate replication fine to each other, but could not replicate from the child DC. The Child DC could replicate from the 2 Parents, but not to them. I spent 3 or 4 days troubleshooting the various Eventvwr logs and repadmin /syncall results, along with pages and pages of dcdiags, netdiags and nltests. Pinging each of the servers was fine by name or IP, and the same for domain name of both domains, nslookup for srv records etc etc.
Things seemed to get worse over time, and eventually I noticed that if I tried to access \\ChildDC from the parent DC my credentials would fail authentication. However if I browsed to \\IP_of_ChildDC it would go straight in.
This lead me back to my initial thought that it a trust issue.
Anyway, after finally looking up the right question; I found out how to fiddle with the automatically generated trust. You have to do this with NetDom in the command prompt.
After typing the following commands:
Netdom trust child.domain.com /Domain:parent.domain /UserD:administrator /PasswordD:* /UserO:administrator /PasswordO:* /reset
Netdom trust parent.domain.com /Domain:child.domain /UserD:administrator /PasswordD:* /UserO:administrator /PasswordO:* /reset
...all seemed well.
repadmin /syncall then produced much more satisfactory results and dcdiag passed on everything bar the existing warnings and errors in the SystemLog.
I hope this helps anyone who has similar issues - I think I lost a lot of hair through this one!