Actually, I am going to go against the flow here and say upgrade. But spend some time researching it before you do this. The time spent here will be saved later in not having to set up every machine again from scratch.

MS did actually put alot of effort into the upgrade process for servers. All of Compaq migrated from NT 4 to 2000 on the server side using upgrades. And from the user perspective, it was trouble free. Not transparent however, as Compaq reduced the domains down to 4 world wide, from the ton that existed from the Compaq/Digital merger.