You need to do a couple of things:
1. Update MAPI/CDO on the BES to match the new Exchange Server
2. Apply the appropriate permissions for BESADmin on the new Exchange Server
3. Ensure that the MAPI profiles can see the new Exchange Server
Here is RIM's KB on it:
BlackBerry Search Results
Let us know if you have any questions.