Exchange or Replication Problem?

About one week ago I lost the ability to add email boxes to my users. It had been functioning correctly until then. I’m still able to add new users and they are able to log on to the domain, however when I go to Exchange Tasks and create a mailbox the email address is no longer being generated. I’ve attempted to manually input the address but it still does not show up in the global address book and will not allow the associated user name to authenticate their name with the Exchange server. I don’t think that Exchange is actually creating the Mailbox, but it also seems partially like a replication issue. Any suggestions?

I’m currently running Windows 2000 AD with Exchange 2000 as the mail server.