Yeah, checked all the permissions myself as well as the CDO versions, then gave a different SA the install guide and KB article and asked him to check it over. Also updated to 4.0.4 and the 2 latest hotfixes.
We're going to wipe everything clean right down to an freshly formatted hard drive for the BES server and start over. Best to do that now while we have only a few test users on board.
If that doesn't work, we'll give RIM a call and see how eager they are to close a sale before the end of the quarter.