Re-install of AD

Our AD server took a dump on us (hard drive crashed). Got a new drive in the server, reinstalled windows, DNS and AD. Got all the users back into AD. When logging into my Terminal Servers from the console, I get an error “Can’t connect. MyCompay not found” (or something like that, can’t remember the specific wording).

Do you think I have something wrong in DNS? or…??