1. Uninstall your BES, search
BlackBerry Technical Solution Center for clean uninstall
2. Install the BES as BESAdmin with the old BES name
3. Restore the old DB
That should get you working, unless you did not create BESAdmin properly.
Also,
1. BES Version
2. Exchange Version
3. MAPI32.dll and CDO.dll on both BES and Exchange