Migrating or Building a new Win 2003 Network from a NT 4.0 network.

Your requirement to retain the existing domain name and profiles rules out building a new network.
Therefore you will have to upgrade the existing one.

A rough plan to do the initial upgrade I have outlined below. I haven't included much detail as I am believer in the "teach a man to fish" rather than "give him a bucket of fish". Information on the exact stages of the upgrade can be found on the Microsoft web site in their white papers.

You will need two machines that you can install NT4 on. These can be anything, from VMWARE to old desktops. They will not remain in production for very long, so don't have to be the best thing available.
You will also need at least one machine that can run Windows 2003 to act as a new domain controller.
Do not attempt this in one weekend, or in one go. It is a complex process that actually requires some waiting around. Unless I am against the clock I will spread the entire process over about three weekends.

1. Build both of the temp machines as NT4 BDCs and add them to the existing network.
Leave them at least overnight to replicate everything.
2. Take one of these BDCs and isolate it - power it down and disconnecting it from the network is enough. This is your backup in case things go wrong.
3. Promote the other machine to PDC. This will turn the existing machine in to a BDC. Again wait a little while for everything to replicate.
4. Carry out an inplace upgrad eon the new PDC to Windows 2003. This will turn your domain in to a Windows 2003 mixed.
5. Build one of the new servers as Windows 2003 and add it to the domain. This should NOT be the machine that is going to run Exc hange. Exchange 2003 is a lot happier on a member server and should be kept that way.
6. DCPROMO this new Windows 2003 machine in to the domain so it become a DC.
7. Transfer all FSMO roles to this new machine, also making it a Global Catalog.
8. DCPROMO out the upgraded machine. Reboot. Drop it in to a workgroup (to remove it from the domain) and then wipe.

The network is now ready to take Exchange 2003. There are a ton of resources at Microsoft on doing the Exchange 5.5 to 2003 upgrade which I don't want to repeat here. That is actually quite an easy process. Basically once you have introduced Exchange 2003 to the network you can replicate the public and system data across, before moving the mailboxes using the Microsoft tools.

You should start here for the documentation: http://www.microsoft.com/technet/prodtechnol/exchange/2003/upgrade.mspx
There is more than enough content there to answer most questions.

For the Windows 2003 migration, you should start here: http://www.microsoft.com/resources/documentation/WindowsServ/2003/all/deployguide/en-us/default.asp
You may also want to look at this guide for an NT4 migration:
http://www.microsoft.com/windowsserver2003/partners/isvs/ntmigrate.mspx

Any questions, please post back.
Simon.

Thank you very much for answering Simon...  Should I install the new NT 4.0 server that will become the PDC with DNS or wait until I've done the upgrade to 2003 on it?  Also, for clarification, should I keep the old PDC now the BDC on the network as I begin the upgrade process, I believe I should if I want to capture the Exchange data off of that server...  But I just want to make sure I'm doing it correctly and not jumping the gun.  Someone else told me to take it off the network and wait until later before bringing it back online.  Is there any benefit in waiting or keeping it in place throughout the upgrade of the other machine?  

Thanks again for your help with this,
Dr. Scott L. Dorsey