We present a case that current observations may already indicate new gravitational physics on cosmological scales. The excess of power seen in the Lyman-alpha forest and small-scale CMB experiments, the anomalously large bulk flows seen both in peculiar velocity surveys and in kinetic SZ, and the higher ISW cross-correlation all indicate that structure may be more evolved than expected from LCDM. We argue that these observations find a natural explanation in models with infinite-volume (or, at least, cosmological-size) extra dimensions, where the graviton is a resonance with a tiny width. The longitudinal mode of the graviton mediates an extra scalar force which speeds up structure formation at late times, thereby accounting for the above anomalies. The required graviton Compton wavelength is relatively small compared to the present Hubble radius, of order 300-600 Mpc. Moreover, with certain assumptions about the behavior of the longitudinal mode on super-Hubble scales, our modified gravity framework can also alleviate the tension with the low quadrupole and the peculiar vanishing of the CMB correlation function on large angular scales, seen both in COBE and WMAP. This relies on a novel mechanism that cancels a late-time ISW contribution against the primordial Sachs-Wolfe amplitude.