You may have indeed two sepparate domains. I am not as good with networking, but I have has this issue only when the SQL Server was not in the domain or in a Netware environment.
When you installed the first windows OS, did you create a domain, ?
when you installed the second OS, did you create a new domain or did you join an existing domain?
You mention creating a domain on both machines, this two domains may not nessesarily be the same domain.
try this site and do a search on this:
www.sqlmag.com
You should be able to find your answer there. It may just be a simple network configuration of making the client a part ot the domain of the server.
When you come back, let us know how you are doing with your issue.
Sal