Try this:
1. Pick a user and enter an appointment on their BB
2. Look in the MAGT log for that users email address around the time you tried the appointment
3. Look for a line with CDO
That line will tell you what the issue is. This issue is always permissions or CDO, seeing as CDO seems ok then it's permissions. If you are positive they are set correctly then the account itself is the issue.
When you create an appointment in Outlook it reaches the BB like an email. When you create an appointment on the BB the account needs permissions to access the mailbox and create the appointment there as well.
Keep this in mind: The BES is on a DC. Is the BESAdmin in any admin groups other than built-in admins? This is the only admin group the BESAdmin can be in and it only works when the BES is on a DC.
Have you reviewed this article?
BlackBerry Search Results
Copy and paste the log lines here if you want, they will tell you exactly what is going on.