Anyone with Win2003 Server Active Direcrtory Experience?

OK.. we have this old server infrastructure at work. Win NT4 SP6 or something.

We want to up date the hardware and so on, and put up a Win 2003 Server with Active Directrory, because we want to use MS Exchange.

WELL... How we are doing this is as follows:

We are adding the Win2003 (with AD) as a secondary domain contorller for an existing domain... Well, the network "dosnt like it". The returned error is something to the effect of:

"An Active Directory domain controller for the domain *** (our domain) cannot be contacted."

DOES this mean... I cannot add a domain controller (of win2003 ad) to an existing network that uses NT4 server (w/o AD)?

jeepers creepers. Can anyone make sense of this... or point me to a resource

How about steps for migration? Ideas?

Thanks