  We compute the contribution of Kaluza-Klein graviton exchange to the cross
section for photon-neutrino scattering. Unlike the usual situation where the
virtual graviton exchange represents a small correction to a leading order
electroweak or strong amplitude, in this case the graviton contribution is of
the same order as the electroweak amplitude, or somewhat larger. Inclusion of
the graviton contribution is not sufficient to allow high energy neutrinos to
scatter from relic neutrinos in processes such as
$\nu\bar{\nu}\to\gamma\gamma$, but the photon-neutrino decoupling temperature
is substantially reduced.
