I agree with the other answer but just to fill in a few blanks. You can build a new BDC with a temporary name and IP, attach it to the network, let it syncronize with the PDC, then promote it to a PDC (this will automatically demote the current PDC) and the old BDC can then be removed from the network and the new BDC assigned it's IP and server name. Let the network stabilize for awhile before you do anything further.
The other machine will be a little more complicated and you have severaloptions. The off-line tape restore will probably work but there are some special considerations with Exchange.
Also, I like to use a new server as an opportunity to build it fresh with a new and unpolluted registry and that means fresh installsof the software and restoring only the data. As long as I have the old server to compare settings, I can build the new server off-line (except for the initial NT BDC part)and then when I'm convinced everything is right, just swap cables and have very little downtime.