Although you can run Exchange 2000 in a Windows 2003 domain, there are some special schema changes that have to be made to the Windows 2000 schema to avoid some potential problems when you upgrade (there's a script available from MS for this, however; go to the MS Knowledgebase web site and look up how to upgrade from Windows 2000 to Windows 2003). And, it cannot run on a Windows 2003 server, only on a Windows 2000 server in a Windows 2003 domain.
I think what you will need to do is install Windows 2003 and upgrade AD, leaving the Exchange server on Windows 2000; then upgrade Exchange 2000 to Exchange 2003; then upgrade the OS on the Exchange server from Windows 2000 to Windows 2003. This is how I am doing it at one of my client sites at the present time. So far, everything has worked out fine.
Hope this helps!