This is the way I did it with mine:
Format/install the new server as a BDC with the name "server_bdc" or something. Get it on the domain, make sure it's working. I seem to recall there were a lot of Microsoft Q-articles I had to read about doing things like stopping and restarting the Server Service on the boxes to make it re-grab the domain database and work properly on the network.
(At each step I had to check the event logs to be certain the boxes were properly on the domain and synching databases right.)
Then, demote "server" to a BDC. Make sure both are working right etc. Perhaps do the stop/start thing again to be sure.
Then, rename the original "server" to "server_old", do the dance to make sure they are all working etc.
Then, rename "server_bdc" to "server", do the dance, then promote it to PDC.
The above is all a little fuzzy because it was a few months ago and there was a lot more involved than that. I pored over the related MS Q-articles and had to do some digging to troubleshoot a couple of snags I ran into along the way. And also, that was a NT3->NT4 migration, I don't know how it's handled on NT5. I don't even know if you can do the BDC/PDC thing with an NT5 box, can you?
Anyone wanna drop by with a 2-4 this weekend?
You couldn't afford my consulting fees and expenses.
edit: But an expenses-paid trip to Newfoundland, would be fun... 