There is an article about this in the blackberry kb: KB16459-BlackBerry smartphone users are unable to send and receive email messages after their Legacy Exchange Distinguished Name attributes were manually changed
but, the example log does look different then yours.
Have your changed the LegacyExchangeDN after the problem appeared ? If yes, maybe revert to the original setting, unless you migrated from Exchange 2003 to 2010, and did not move the public folders prior to uninstalling exchange 2003.
Does it make a difference when you want to add the user to the BES you choose "add user from company" directory instead of just clicking on the user ?
Beside this, I dont have any in depth knowlege what to do if there is really a problem with the LegacyExchangeDN, if it is not becaus of a incomplete migration from 2003.
There is always the option to backup the mailbox to a pst file, delete the user, create a new user and upload the pst to the mailbox. This should fix the problem most likely.
The only drawback with this method might be, that the user is probably not able to reply to old emails or old appointment invites.