No longer can add computers to domain

We have a client that has a 2000 server using active directory which we have been able to add new computers to the their domain in the past. They have just recently purchased new computers and all of a sudden adding new computers to the domain the server refuses the join. The only error we see is that we cannot join the domain from the client and the message The specified server cannot perform the requested operation”. What can we look at on why this could be happening. One new computer is a windows 2003 server but is NOT acting as a PDC, active direcotory or anything as such to our knowledge except for just a server level machine for backups and such. Please help.