If gravity worked differently across large distances, would that solve the mystery of dark matter?
I can't say that it's impossible. Alternative ideas have been offered to challenge even extremely well-tested theories like general relativity. It's actually not so difficult to come up with an alternative theory that explains the observations better than the standard theory, since you can always fine-tune parameters in the alternative theory to match what's observed. One could even make the case that alternative theories of gravitation aren't any more ad hoc than a standard model that includes both dark matter and dark energy that we're as yet unable to identify!
But the standard "cold dark matter" scenario actually does an excellent job of explaining the structure of the universe across a broad range of scales. Any competing theory would have to explain that just as well. And in fact, the ultimate test of an alternative theory is whether it can both explain existing observations *and* predict the results of future observations better than the standard model. So far, no alternative explanation has been able to predict the results of observations convincingly enough for most astronomers and physicists to doubt the existence of dark matter.
Update: Since posting this answer, I've been reminded that gravitational lensing observations of galaxies show pretty conclusively that not all the matter in galaxies is in the stars. That is, we know that gravity bends light. And there appears to be bending of light happening on the outskirts of galaxies where there aren't any stars. This provides a pretty serious problem for any theory that's offering an alternative to dark matter.
This page was last updated June 27, 2015.