Here are the steps to take, and the order in which to take them if you want to rename a server that has MOSS already installed and configured on it:
*** NOTE: Use only letters, digits and minus for the machine name (so no underscores), max 15 characters.
Your server is now renamed.