Wow. I set out to establish a domain trust between ServerB and ServerA. The computer name and domain name of ServerA have both been renamed in the past. I ran into problems: the trust wizard thought I was trying to establish a trust w/ the same domain that it was running on (ServerB's domain name matched ServerA's former domain name). When renaming the domain earlier, I had forgotten to run netdom /clean and netdom /end. Before discovering this oversight, I used netdom to update ServerA's FQDN, did a search-and-replace on my DNS files to remove all references to the old domain name, tried tinkering w/ NTDSUtil and ADSIEdit, and felt very frustrated!
After resolving that issue, I received a different error message stating that my target was "not a valid Windows domain". This was solved by adding conditional forwarding to the DNS server in each domain. Now I could establish a trust relationship.
After the two-way trust was setup, all was well for users on ServerB. However, when ServerA users tried to browse ServerB by name, an error occurred "Logon Failure: The target account name is incorrect". Running nslookup on ServerA revealed a problem w/ DNS ("Can't find server name for address x.x.x.x: Timed out"). I manually recreated a reverse lookup zone in DNS on ServerA (now nslookup reported "...Non-existant domain"), ran ipconfig /registerdns, and restarted the NetLogon service. That fixed the DNS problem (hurray!), but not the "Logon Failure".
Eventually, I found that a computer account for ServerB was present in ADUC on ServerA. Deleting that account solved the problem! This exercise has taken about five hours over two days.
