It's not that they can't both be right (in fact, both are correct, insofar as calling a theory "correct" makes sense in physics), it's that they break down in certain regimes. This is the absolute last thing from surprising: every single physical theory we know of so far breaks down at some point. Newtonian mechanics breaks down at high speeds (relative to c). Classical mechanics breaks down in the quantum limit, and is replaced by quantum mechanics. Quantum mechanics breaks down in the relativistic limit (and is replaced by quantum field theory). Most QFT breaks down at high energies, as we can only solve it in the pertubative low-energy limit.
In the case of GR and quantum mechanics, that's exactly what happens. At low energies, the two work together fine. It's at high energies and short length-scales where the two fall apart (no surprise, as again, both theories were formulated from the low-energy behavior, which is the regime we can perform experiments/observations in quite easily). This is why people are looking for some unified theory that would include both theories in the low-energy regime, and at the same time would work at high energies (this has already been done with electrodynamics and the weak force: at high energies, they become unified through the electroweak interaction). String theory, loop quantum gravity, etc. are all such attempts. So far, we've not been able to perform experiments that would be required to confirm any of them.