Exchange server headach

My boss has decided to change the name of the company.

He is also wants us to have all new email addresses. I am trying to get my exchange 2003 install to accept emails from a new domain.

Mail.newcompanyname.com and creat new email account to refelct the new internet domain.

I would like some help wiht the pitfalls here I am sure someone else had to have done this before.