Do you restore to the remote server or on the itself? Do you have 1 DC or more?If you have more than one, and rebuild the server identical with the previous one, then I think there is a AD replication issue, if it's a single DC, you may want to go to the service and make sure all backup exec service log on by the administrator and open exhange manager right click on the server in security, check the permission on the server make sure the whatever backup account has full controll. Good luck