Adding a domain to a workstation

When I attempt to add a machine to a domain, I get the message that the computer is already a member; but it is not. The domain name does not come up in the list of domains available to log on to. I have added the machine to the domain using server manager and then removed it and added it back. No luck. We are running NT 4.0.I am logged on as and administrator with permission to add domains. Any ideas?