No worries we wil make besadmin out of you

. Before you start changing things to fix it, look at what might have changed to cause it. You need a really good understanding of your existing architecture before you can understand what effect changes can/will have.
So I would be looking at the following things to get you going, we can get into details later -
1. when did this start?
2. do you know of anything at all on the BES or Exchange servers which has changed since then? Nothing is too small a change to be relevant (well, nearly nothing)
3. could anyone have changed any Exchange permissions which would cause this (specifically the access besadmin has to Exchange)
I am wondering if you just applied the latest Exchange security patch and that has caused an issue. Find out if you did and if yes, was it on Exch only or Exch and BES.
It might be handy to know your MAPI32.dll and CDO.dll versions from Exch and BES now, just in case.