Check the MDAC version on the SQL server and the BES server. I had kind of the same issues, here is my Blackberry Support reply;
The MDAC v2.8 requirement is listed as a prerequisite on page 9 of the Installation Guide for BlackBerry Enterprise Server v4.0.
"Download Microsoft Data Access Components (MDAC) 2.8 from
and install it on the
BlackBerry Enterprise Server computer and on the server where the configuration database is located."
It may be possible to use MSDE 2000 to house the BlackBerry
Configuration Database, however it would not be recommended if you have a large amount of users due to the resource and performance limitations of MSDE.
Alternatively, since you have not yet upgraded to BlackBerry Enterprise Server v4.0, you may want to drop the existing BESMgmt database andcreate a new one using the CreateDB.exe scripts for BlackBerry Enterprise Server v4.0. The v3.6 BlackBerry Enterprise Server will continue to run without the database, however the BlackBerry Management Console will be unavailable until the database is recreated, and after
the database has been upgraded, the BlackBerry Manager will need to be used for administration. By dropping and creating a new database, once you upgrade to BlackBerry Enterprise Server v4.0, you will also have to recreate your IT Policies and any custom Mobile Data Service settings.