You must be running at a functional level of Widnows 2000 native or Windows 2003. This does not mean you cannot have NT 4.0 servers. It simply means all your domain controllers must be at Windows 2000 or higher. Your forest functional level however must be at Windows server 2003.
This being said the domain controller that holds the schema master role must be at windows 2003 SP1. At least one global catalog server in each site also needs to be running Windows 2003 sp1.
There is also an Exchange functional level which must be set to native. This has nothing to do with the domain native mode. It simply means there are no more Exchange 5.5 servers in your organization.
To switch to Exchange native mode follow these steps:
*You should be absolutely sure you do not need Exchange 5.5 servers before flipping the switch it is not possible to go back.
Depending on how accounts were migrated to Exchange 2003 you may have duplicates for every user in your organization. You can merge these duplicates using a tool called ADClean it is located in teh exchsrvr/bin directory.