  In this letter we compute stringent astrophysical and cosmological
constraints on a recently proposed Eddington-inspired Born-Infeld theory of
gravity. We find, using a generalized version of the Zel'dovich approximation,
that in this theory a pressureless cold dark matter fluid has a non-zero
effective sound speed. We compute the corresponding effective Jeans length and
show that it is approximately equal to the fundamental length of the theory
$R_*=\kappa^{1/2} G^{-1/2}$, where $\kappa$ is the only additional parameter of
theory with respect to general relativity and $G$ is the gravitational
constant. This scale determines the minimum size of compact objects which are
held together by gravity. We also estimate the critical mass above which
pressureless compact objects are unstable to colapse into a black hole, showing
that it is approximately equal to the fundamental mass $M_* = \kappa^{1/2} c^2
G^{-3/2}$, and we show that the maximum density attainable inside stable
compact stars is roughly equal to the fundamental density $\rho_*=\kappa^{-1}
c^2$, where $c$ is the speed of light in vacuum. We find that the mere
existence of astrophysical objects of size $R$ which are held together by their
own gravity leads to the constraint $\kappa < G R^2$. In the case of neutron
stars this implies that $\kappa < 10^{-2} \, {\rm m^5 \, kg^{-1} \, s^{-2}}$, a
limit which is stronger by about 10 orders of magnitude than big bang
nucleosynthesis constraints and by more than 7 orders of magnitude than solar
constraints.
