One of the motivations of having larger extra dimensions is to solve the hierarchy problem on physics. In particular to answer the question of why is gravity so much weaker than the other forces. The extra dimensions solve this problem by saving that gravity inherently just as strong as the other forces but it leaks into the extra dimensions reducing its efficacy on scales larger than the extra dimensions. This is either the physical size of the extra dimension (in a Kaluza-Klein picture) or the scale of the warping of the extra dimension in a Randall-Sundrum. picture. The authors argue that one consequence of this it is that black holes would evaporate much more quickly in this scenario. As the black hole in a binary loses mass, the size of the binary orbit must increase with the orbital period. On the other hand, the emission of gravitational radiation causes the orbital period to decrease. The measurement of the period change in such a system could tell whether evaporation or radiation dominates.
One concern that I have with paper is that they apparently assume that the mass loss is isotropic, so the angular momentum of the system is conserved; however, I think that in reality the mass lost from the black hole will carry the specific angular momentum of the black hole. This might be what they mean by isotropic, but since they don't derive the change in orbital parameters I'm not sure. I don't think that this is a major issue because the product of the total mass and the semi-major axis is an adiabatic invariant, so as the total mass decreases, the semi-major axis and the period must increase. This may change some of the details but not the general conclusions.
arXiv:1010.5245 [pdf, ps, other] Title: A Precision Test for an Extra Spatial Dimension Using Black Hole--Pulsar Binaries