when adding a new user an exchange mailbox will not create

I am using SBS 2003, when I create a new user in AD the mailbox will not create in exchange even though the check box is selected. The new user can log on to the domain with the new account but outlook will not resolve the name to create a mailbox. Any suggestions for a fix?