Stolen windows 2003 server. New server with the same domain name

Hello to everyone
Please consider this scenario:
The only domain controller “server” is lost. We have a new server with windows 2003 standard installed with the same domain name as before. I have created the users and passwords in AD and users can login but of course AD was not migrated. Is there a better solution then having all workstations to rejoin the same name and loose their profiles? I know about copying the profiles but that is a long process. Please let me know if there is a better solution.
Thank you all and I’m very exited about joining the group.