Moving primary domain controller to new server

Solution 1:

• Add new computer to domain
• Promote system to a domain controller (dcpromo)
• Transfer FSMO roles
• Verify/Make the new system a Global Catalog.
• Wait some time for replication to take place. Run dcdiag/repadmin and so on to make sure everything transferred
• Demote old system (dcpromo)
• Double check DNS zones & AD to make sure old system was removed.

Migrate any other data or services as needed.

Of course you could leave the old system up so you have another spare DC.

Solution 2:

In addition to what Zoredache stated in his answer, make sure to update all of the domain clients to use the new DC for DNS.

On a side note, if the original DC you're replacing is the only DC in the domain, then running DCPROMO on the original DC will transfer the FSMO roles to the new DC without the need to manually transfer them. If it's not the only DC in the domain, then DCPROMO will transfer the FSMO roles to another DC, I'm just not sure how it selects the DC to assume the roles.