This is a hard one Kenshi, it is very bad that the Server HD died... The problem you have in reinstalling a new server is all the client pc's which are connected to your domain will have SIDs and profiles...

As you've discovered, you simply cannot make a new server and try to fool the Client PCs, although it would be nice...

BB's suggestion is good, but you could also try the built-in connect computer to domain wizard...

on each Client PC, open IE, and http://servername/connectcomputer

it should reconnect the PC to the domain, however, the issue could be the loss of profile settings and it trys to make a new profile and SID... if you have roaming profiles you might be OK

Dehc and Curio are good people to ask about this server stuff.