For this post I will assume that the observation of neutrinos faster than light is accurate and not further mention this assumption below.
Of the particles whose speeds have been accurately measured, the neutrino is unique in that it does not participate in electromagnetic interactions. The graviton also does not participate in electromagnetic interactions and so we might expect its velocity to also exceed that of light. This has immediate impact on quantum gravity and would open up a wide range of new theories.
Since neutrinos can be used to send a signal, their moving faster than light destroys the relationship between causality and arbitrary reference frames which forms an important part of the special theory of relativity. To get causality to function again, we have to choose one reference frame as the preferred one and then let that reference frame define causality for all others. This variation of the special theory of relativity is sometimes called "Lorentzian Relativity" or "neo-Lorentzian Relativity" or "Lorentz Ether Theory", and has been explored by fringe physicists for most of the last 100 years.
The presence of a preferred reference frame in the special theory of relativity implies that one must also be present in general relativity. This makes theories that assume a "background metric" more interesting. Of such theories, my favorite is the one found by the Cambridge Geometric Algebra Research Group. For example, see Gravity, Gauge Theories and Geometric Algebra, Anthony Lasenby, Chris Doran, Stephen Gull, Phil. Trans. R. Soc. Lond. A 356, 487-582 (1998). This theory gives the observable predictions of GR exactly, but avoids wormholes and other topological things as it is built on a flat background metric. Rather than tensors, it uses the gamma matrices used in the rest of particle physics.
In terms of the damage to relativity as compared to the damage to quantum mechanics, an accepted observation of superluminal neutrinos would be more damaging to relativity. So I would think that the general effect on quantum gravity would be to make it more quantum and less (traditional) gravity.