The mounting evidence for anomalously large peculiar velocities in our Universe presents a challenge for the LCDM paradigm. The recent estimates of the large scale bulk flow by Watkins et al. are inconsistent at the nearly 3 sigma level with LCDM predictions. Meanwhile, Lee and Komatsu have recently estimated that the occurrence of high-velocity merging systems such as the Bullet Cluster (1E0657-57) is unlikely at a 6.5-5.8 sigma level, with an estimated probability between 3.3x10^{-11} and 3.6x10^{-9} in LCDM cosmology. We show that these anomalies are alleviated in a broad class of infrared-modifed gravity theories, called brane-induced gravity, in which gravity becomes higher-dimensional at ultra large distances. These theories include additional scalar forces that enhance gravitational attraction and therefore speed up structure formation at late times and on sufficiently large scales. The peculiar velocities are enhanced by 24-34% compared to standard gravity, with the maximal enhancement nearly consistent at the 2 sigma level with bulk flow observations. The occurrence of the Bullet Cluster in these theories is 10^4 times more probable than in LCDM cosmology.

15 pages, 6 figures. v2: added references