Open up your Admin program for exch.
Check the following properites:
Top levels (global - site - and server) Make sure that the exchange user has the appropiate rights. Should be Service Account Admin.
Next check the Recipients Container that you are trying to create the mb in. Make sure that you have rights to that container.
Next, have you changed your password lately?
And did you synch the domain?
Is the PDC available??? --> exchange talks directly to the PDC, regardless ofwhether or not there is a bdc online or if _that_ server is a bdc.
Are ALL exchnage services running? If not which ones are not? (chat and lotus notes do not need to be running)
Is the workstation and server services running on that server?
Just some places to look at.