Hmm ok well if you checked all your steps, are happy that perms are all set correctly and you did all the work as besadmin and not you, it's time to get checking the BES logs. Do have a good search on here first though as it must have happened before, although I can't recall this same scenario tbh. Personally I have only seen this scenario happen a lot in reverse (BB can't update but outlook can), and that is usually solved by perms or CDO/MAPI32. I have to think it's happened before though....
I was a BES and Exchange admin once.
Then my world turned Blue.