You can check a few things
1. Make sure your domain trust(s) are still in place and functioning correctly. If you don't have the W2K support tools installed (ie in a prod environment), run dsa.msc and check that you can browse the remote domain and list groups and users in the remote domain (eg attempt to add a global group from the remote domain to a local domain group - you can do this with committing the change)
2. Make sure the account you are using has a valid SQL Server login on the remote SQL Server (or your account is in the builtin admins group on the remote server - if the other domain are willing to trust you with local admins on the remote server or the remote domain)

Are both domains in W2K native or do you have W2K and W2K3 forests in the mix?