New 2003 server in NT domain

Yes.  Copy off all data you need from the original PDC.  Use a workstation temporarily to install NT4 as a BDC, then promote it to PDC after removing the old PDC.  Upgrade it to 2003 with DNS installed during the DCPROMO.   Make sure your DNS zones are AD Integrated.

Add your new server as a DC, install DNS and allow it to replicate from the temporary server, then transfer all the roles from the temporary server to this new one.  Don't forget to make it a GC as well.

Copy your data back that you saved from your old PDC.  Obviously, this means you should have copied it to a worksation with a large hard drive so it can be retrieved easily.  You may want to use ROBOCOPY or XCOPY to preserve any ACLs on the data.

Once the new server is stable, then DCPROMO (demote) the temporary server out of the domain.

Remove all DNS entries for the temporary server.  Remove any server object for this machine from AD Sites and Services.

You should be good to move forward now.  Make sure you DO NOT change the domain or forest functional levels from the defaults until ALL your NT4 domain controllers are gone for good.

Is there a way to leave my existing nt domain the way it is temporarily, install 2003 server on the new server and create another domain.  Once this is done can I transfer things slowly over to the new domain and once I have everything that I want, then rename the new domain back to the old NT domain name?

You can, but renaming the domain is not a trivial job.  It can be done, but I haven't run into anyone that hasn't had some issues.  

Remember that your AD namespace doesn't need to be a public namespace.  If your domain is called "johnson" in the NT world, then name the new domain "johnsons.local" - the NetBIOS name of the domain must be different and the extension should be something non-public.

AD Namespace is only for domain functionality - nothing else.  It doesn't need to even be remotely similar to the external name.

You can install 2003 in a new Forest and Domain as a parallel installation.  The use ADMT to migrate everyone over.

I would really think twice about a domain rename after you're done.  If you hose things at that point then everything's gone.

I am having trouble with setting up a two way trust between the NT domain and the 2003 domain.  On the NT side it lets me add the 2003 domain in the "trusting domains", but when I try to add the 2003 domain as a "trusted domain" it says the domain controller can not be contacted.  Any suggestions?

You may need to add the other domain to an LMHOSTS or HOSTS file (or both).

You need perfect resolution to make this work.

Is it possible to reload 2003 on the new server, make it a member server in the existing NT domain, then copy data and all security information to it from the existing PDC?  Then promote it to be the PDC of the existing network?

No.

A 2003 cannot participate in an NT4 domain as a domain controller.  As a member, yes, but that doesn't help you out much.

Can I promote it to the PDC at a later time after it is already a member?

Thanks for the suggestions.  I will try it and let you know what happens.  Thanks!

I have not had a chance to try it yet.  There has been no sufficient downtime yet.  I will update you soon.  Thanks.