Is your forest running in Native or Mixed Mode?
2000 Active Directory is a nasty beast when running in Mixed Mode.
In the Active Directory Users and Computers, did you add that domains admins into the the enterprise admins group?
There may be issues with pre-w2k domains because they are not using Active Directory. Which is a key foundation to browsing thru the forest. NT4 knows nothing about active directory and from what I can tell will choke.
Try pointing the NT domain controllers DNS to the Active Directory Based DNS server.
There is one thing that I read in the ms accelerated exam book, Non-win2k clients can not benefit from transitive trust, they are limited to the limitiations of pre-w2k trust relationships access toresources.
(pgs 448-449)
With that in mind check the trust relationships on the nt4 pdc.
From everything I have read so far, MS expects you to upgrade your pdc to 2k then move your bdcs and member servers. It is very cryptic about NT4 PDCs <--> W2k DCs
Good luck - thanks though, now you have given me another lab to try.