Give this a look: Migrate from Exchange 2000 to 2003 in a BlackBerry Enterprise Server 4.0 or 4.1 environment
Simply put you need to do the following:
1) Grant the BESAdmin account permissions on the new Exchange Server
2) Replace the Exchange MAPI / CDO components on BES with 2003 components, making sure it is at or above the patch level of your Exchange 2003 Server. You don't want to simply copy the files from Exchange, but rather install them much in the same way you did on your Exchange server.
3) Move the users (and run a handheldcleanup)