Indeed, this is the observation most usually cited in support of the matter / particle interpretation of dark matter. It's very non trivial to come up with a decent theoretical extension to GR that explains it. Which is why, I think, that a lot of people feel more confident proposing a new dark matter particle, which does in fact explain it quite nicely.

Perhaps we're wrong in assuming that all of these observations on very different scales (galaxy rotation curves over galaxy cluster collisions to large scale structure) are tied to the same unknown (dark matter), but if you want to explain them all in a simple way, a particle still seems like the way to go.

Remember that elementary particles have been predicted and found many times over the past years, whereas modified theories of gravity haven't seen the same kind of success. Of course this is only anecdotal, and may not mean anything, but I think it's part of the reason for most people's preference for a particle explanation.