Exchange server link to WinNT server

I have been ask by a friend, if I had a solution to an exchange server 5.5 problem, at his job.
The main server (win NT4) crash and was reinstall, the Ghost could not work on the new machine.
Since this the exchange server can't reconnect to the domain server, it see it on the network.
The message has something to do with access denied.
Consultant on exchange say not much chance to fix, and suggested to reinstall everythings.
Where to start? I should be able to get more information if needed.