Cannot Join Domain

I am trying to add a new machine to my domain, and I get the error “cannot find domain controller for this domain”. From the PDC and BDC, I can ping this new machine, both by name, and IP. However, from the BDC I cannot ping this new machine, but I can from the PDC. (The BDC is the domain controller here)
Any help would be appreciated.