In theories with universal extra dimensions (UEDs), all standard model fields propagate in the bulk and the lightest state of the first Kaluza-Klein (KK) level can be made stable by imposing a Z2 parity. We consider a framework where the lightest KK particle (LKP) is a neutral, extremely weakly interacting particle such as the first KK excitation of the graviton, while the next-to-lightest KK particle (NLKP) is the first KK mode of a charged right-handed lepton. In such a scenario, due to its very small couplings to the LKP, the NLKP is long-lived. We investigate the production of these particles from the interaction of high energy neutrinos with nucleons in the Earth, and determine the rate of NLKP events in neutrino telescopes. Using the Waxman-Bahcall limit for the neutrino flux, we find that the rate can be as large as a few hundreds events a year for realistic values of the NLKP mass.