Are both domains Win2k AD domains? If so are you typing the entire AD domain name when trying to create the trust. Check the NetBIOS domain names for both domains. If the default was accepted when the AD domain names were created, the NetBIOS domain names are both "Sample." While I can't find anything specific documented in the MS Knowledgebase, I suspect your problem relates to this conflict. Unfortunately, the only way to change a domain name (either NetBIOS or DNS/AD) is to run dcpromo (which effectively deletes the domain) to demote the server and then running it again to promote the server (and create a domain with a different name)
If one of the domains is an NT domain, the problem is definitely a NetBIOS domain name conflictas NT only recognizes NetBIOS domain names.
Hope this helps.