I am getting an error that says I either do not have permissions to the users mailbox or that it has been deleted.

Edit: All activity on account had stopped at one point for an unknown reason, user was removed to be re-added in an attempt to get it working again.

The mailbox is still there, and the account is a domain admin account which has the rights to exchange. I also had just added a user the week before. Any ideas?

This is the CEO of the company who the error is occuring on so I need to get it fixed ASAP. I would appreciate a quick response on this matter. Thanks.

what account are you logged into the BlackBerry Enterprise Server as? What account was the BlackBerry Enterprise Server services running as?

What access does the account have within Exchange?