We had a problem with exchange, and had to repair our Information Store. After getting exchange running, I'm getting an
error on only some of the blackberry users.
Unable to access the mailbox for this user.

we're running Windows server '03 exchange '03 and BeS 4.0.6

I have tried deleting a user and re-adding them in blackberry manager, I get "Failed to add user "username" to the Blackberry Server. Unable to open mailbox for user.
The user's mailbox may have been deleted."

I have run IEMSTest and it said it was successful on all of the users.

Any suggestions would be helpful

Have you rebooted the BES since your Exchange issues have been resolved?

yeah, a couple of times actually. Initially none of the blackberries where receiving messages, after restarting most of them worked, but a few are getting the "unable to access mailbox error."

How many is some?

If you are sure that all is right with the perms, that the mailbox is good and can be accessed/used via Outlook/OWA/etc, then you may need to run DBCLEAN from a workstation (not the server) for the user(s).

Read this:
KB04189 - When adding a BlackBerry smartphone user to the BlackBerry Manager it ...

HDAWG's post here with dbclean link:
can't get a user to activate fully

And here it is again:
http://www.port3101.org/download/tools/dbclean.exe