  The existence of extra dimensions allows the possibility that the fundamental
scale of gravity is at the TeV. If that is the case, gravity could dominate the
interactions of ultra-high energy cosmic rays. In particular, the production of
microscopic black holes by cosmogenic neutrinos has been estimated in a number
of papers. We consider here gravity-mediated interactions at larger distances,
where they can be calculated in the eikonal approximation. We show that for the
expected flux of cosmogenic neutrinos these elastic processes give a stronger
signal than black hole production in neutrino telescopes. Taking the bounds on
the higher dimensional Planck mass M_D (D=4+n) from current air shower
experiments, for n=2 (6) elastic collisions could produce up to 118 (34) events
per year at IceCube. On the other hand, the absence of any signal would imply a
bound of M_D>~5 TeV.
