new user account problem

When you are creating those accounts, do you check the box to say the account is mail-enabled?

but in my case this was a second server taking over from an old one I was replacing.

I had to go through a few TechNet articles relating to all the tasks you need to complete to remove an exchange server, and one of them was moving the Recipient Update Server. If this isn't done, than although you see all the correct mailbox info in the AD U&C, there is no mailbox.

Does this help?

I have had this problem on several occasions after windows updates, I have my servers set to not restart after windows updates occasionally because all my DCs update at the same time as does the exchange server I get some funky behavior out of the Exchange server, won't take new boxes or won't update a group. Seems to me that it loses its ability to read from the Global Catalog server, I have just shut down my DCs one at a time then the exchange server and re-start it. Email goes down for about 5 minutes then you can create the box again.

Is this a new Installation?

You are going to have to re-install exchange.. and it's a pain, if you can build your domain again I would start from scratch rather then pulling EXCHANGE off. Make sure you run the forest prep and domain prep and READ the logfiles they generate. I build a seperate user called EXCK2k3MS that is a memeber of the domain admin group and run all the services/applications and domain interactions with "his" authority. It keeps the installation neater, then you can change your administrator password without the service headaches it will cause in exchange.--> make the password like 25 characters and as cryptic as possible then DOCUMENT it. I like to use Song lyrics find a song you like and a verse then first letter of each word then change the vouls to numbers and certain letters to symbols for example s=& c=( q=@ l=! k=%