The specific case that I found is:
PowerMod[411728896, 1/411728896, 10^9]
which returns:
PowerMod::root: The equation x^411728896 = 411728896 (mod 1000000000) has no integer solutions. >>
However, a solution is x=4.
Solve[ x^411728896 == 411728896, x, Integers, Modulus -> 10^9]
Solve::mdom: Warning: Mathematica is ignoring domain specification Integers; option setting Modulus -> 1000000000 implies domain integers modulo 1000000000. >>
Roots::lrgexp: Exponent is out of bounds for function Roots. >>
Solve::munsp: Solve was unable to solve the system. Increasing the value of "MaxModularPoints" in SystemOptions["ReduceOptions"] may help. >>
Not sure how I missed this. Yes, this is a bug. Will get looked at.