I just had this problem. I am assuming that you are using a BES. the CDO.DLL (%systemroot%\system32) on your BES server and your Exchange server must be the same version. I stopped all Blackberry services, copied the CDO.DLL from the exchange server to the BES Server, overwriting the existing one. Then either reboot the BES or re-start the services, and everything should be working fine.
Hope that helps