I hate to differ...
If you are rebuilding a server from scratch, save all of your databases, save your id files for at leaset the admin and save your cert.id file. If you are going to re-install the same version of Notes, save everything in your data folder to be exact.
Re-install the server software. Before launching the server for the first time, copy the information from your data folder back into the data directory.
If you saved notes.ini, copy if back to the directory before data, ie. notes or Lotus\domino.
Now then. If you are trying to get to run the setup program, launch the server. If you are not, delete setup.nsf from the directory, then launch the domino server.
In doing this, you can move Domino from one machine to another, or from one OS to another without having to resetup or re-sign the datebases.
What was suggested in the earlier post could cause you a great deal of pain, especially if you just arbitrarily change the server name. You could do it by registering another server id, but if you are going to do that, then I would simply set up the new server with the new ID, replicate the databases, move the users, then decomission the old server (Read the help file on doing this). If you are not going to leave the old server in production, you are not going to have any licensing issues in doing this.
If you are moving to a new OS, IE, NT to W2K, I would suggest moving and re-installing with the old version of the software, and then upgrading the server to the proper release AFTER you have confirmed that you can bring it up. If this is your case, remember that anything less than 5.0.7a does not run properly on w2k (it will run, just very slowly and you will have other issues that creep up the longer the server is up.), in fact, you really need to just move all the way up to 5.0.11