Changing Domain in Exchange server 2003

My boss is planning to change the name of the company. He wants all the email address to reflect that change. We are getting a new webdomain set up to reflect the new name, but I am not sure how to reconfigure the exchange server. Its exchange 2003 running on Windows 2003 server.

This also means that everyone is going to need new email addresses or if I can alter them inside the server.

Look I know I look like an idiot posting like this but I am getting conflicting advise from various sources. So any guidence from somone who has done this before would be welcomed.