IIRC, you can only add a user from another domain to a local group, not a global group. If the other domain is within the same forest, you can add them to a universal group as well as IIRC, the global catalog will help enumerate those users.
A quick test is to try adding a user from the 2K domain to the NTFS permissions of a folder on the domain controller's local drive. Are you able to see the 2K domain and add the user? If not, you have an issue with the trust.
RebateMonger or someone else can correct me if I'm wrong; it has been a few years since I managed a domain with multiple trusts.