client not connecting to domain

One of our client pcs, that was in the domain , had to be formatted. When i tried adding it back to the domain after the formatting, it says, the domain controller could not be contacted.

I am able to ping to and from the server to this client pc. I can access the internet and shared folders in the network from this pc. I have disabled the firewall also. Just cant seem to figure out where the hindrance is. I tried changing the computer name and also the Ip, if that was the reason it was conflicting.

Please help asap.

Thanks and regards,
Has