This paper investigates the physics reach of the IceCube neutrino detector when it will have collected a data set of order one million atmospheric neutrinos with energies in the 0.1 \sim 10^4 TeV range. The paper consists of three parts. We first demonstrate how to simulate the detector performance using relatively simple analytic methods. Because of the high energies of the neutrinos, their oscillations, propagation in the Earth and regeneration due to \tau decay must be treated in a coherent way. We set up the formalism to do this and discuss the implications. In a final section we apply the methods developed to evaluate the potential of IceCube to study new physics beyond neutrino oscillations. Not surprisingly, because of the increased energy and statistics over present experiments, existing bounds on violations of the equivalence principle and of Lorentz invariance can be improved by over two orders of magnitude. The methods developed can be readily applied to other non-conventional physics associated with neutrinos.