Exchange 5.5 Problem

Hi, I rebuilt/restored my Exchange 5.5 server and users in it’s home domain can log in fine, but users in other domains can not. They get an error that they do not have the necessary permissions to log in. They used to be able to before the rebuild.
Any ideas.
-MLevy