  In light of recent measurements of the nucleon structure function in the
small-$x$ deep-inelastic regime at HERA and the consequently improved
theoretical understanding of the quark distributions in this range of parton
fractional momentum, we present new results for the neutrino-nucleon cross
section at ultra high energies, up to $ E_{\nu} \sim 10^{21}$ eV. The results
are relevant to deep underground muon detectors looking for such neutrinos. For
$\simeq 10^{20}$ eV neutrinos, our cross sections are about a factor of $4$ to
$10$ times larger than the previously reported results by Reno, Quigg and
Walker. We discuss implications of this new neutrino-nucleon cross section for
a variety of current and future neutrino detectors.
