Without more information it is difficult to say. However, the trust relationships between Windows NT domains and Windows 2000/2003 domains can get into problems. Windows NT of course, relies much more heavily on WINS for name resolution and location of services. Windows 2000+ focuses on DNS. I have run into cases where I have see issues similar to the ones you have mentioned, and had to create LMHOSTS files on the Windows 2000+ machines and the Windows NT machines to make sure that the systems could see each other. The LMHOSTS would need to contain the domain controllers of the Windows NT domains and the PDC emulators from each of the Windows 2000+ domains. The NT machines will not communicate trust relationships with the other DCs in a Windows 2000+ domain, only the one with the PDC Emulator FSMO role. This may resolve all of the issues, aside from the Schmea Mismatch issue.
Schema Mismatch may be more indicative of a replication issue. Check on the replication between DC’s and also check the FSMO roles in relation to Global Catalog servers. Recall that in a complex domain forest it is very important that the Infrastructure Master is NOT a Global Catalog Server.