OK, first things first. If you have moved any mailboxes to the new server, move them back. The process I will detail should be done when you can have your e-mail down for up to four hours.
1. Backup the existing server.
2. Run the optimizer on the server and note where databases and log files are currently kept - do not allow any changes.
3. Remove the new server from the site.
4. Ensure there is a local administrator account on the existing server, then set all Exchange services to manual startup.
5. Change the server name.
6. At the PDC, remove the computer name from the domain using server manager. Keep in mind that it can take up to two hours for the server name to disappear.
7. Ensure there is a local admin account on the new server.
8. Uninstall Exchange from the new server.
9. Delete the 'new' servers name from the domain.
10. Change the new servers name to that of the old server and join it to the domain.
11. Ensure NT is at the appropriate service pack level.
12. Install Exchange server on the new server being sure to duplicate the Organization, Site, and Server names that were used on the original server.
13. Install the exchange service pack at the same level as the original server or higher (if the old server was running Exchange SP3, you must at least apply SP3, or you can apply SP4).
14. Run the optimizer and ensure that the databases and log files are put on the same drives as they were on the original server. If you don't have drive letters matching the old server, remedy that situation before proceeding. If necessary, re-install the OS so that this can be done.
15. Set all Exchange services to manual startup.
16. Locate the following folders on all drives: x:\exchsrvr\mdbdata, x:\exchsrvr\mtadata, x:\exchsrvr\dsadata. In each of these folders create a folder named 'Hold'. Open this folder separately and move the contents of the upper-level folder (dsadata, for example) into the hold folder. Do this for each of the above folders on all drives.
17. Connect the the old Exchange server and connect to the root of each drive.
18. Copy (DO NOT MOVE) the contents of the folders listed in step 16 to the corresponding folders on the new server. IT IS IMPORTANT that you pay close attention to copying from C: to C:, etc.
19. Open a DOS window and change to C:\Exchsrvr\bin. Then, run the command 'Isinteg -patch' (without the quotes). You should receive a message that the database was successfully updated.
20. Start the Exchange services.
I have performed this procedure numerous times, and have detailed it here from memory. If you have access to TechNet, reference article Q155216. It is not currently available online.
This is the preferred method for replacing an Exchange server with new hardware. If you were to move mailboxes from one server to another, your users would never actually know, but you would lose your single instance for attachments and would end up using much more disk space. This method is cleaner and faster. It also has the advantage that your old server can be brought online as a backup, as long as you go through the process of deleting and re-adding the server name from the domain as detailed above. This is due to each physical machine getting a different SID. Without doing this, the old server would not be recognized.
Good luck!