Trouble accessing after a Restore

After our NT Server’s HD failed, we did a restore to recover our information. Now, all of the computers appear in network neighborhood appear, but we cannot access two of them. However, these two can still see out onto the rest of the network. Also, every time we log into these two computers, we get the following error: “A domain controller for your domain could not be contacted. You have logged on using cached account information.” Any suggestions on what I am doing wrong?