In the universal extra dimensions (UED) scenario, the tree level masses of the first level Kaluza-Klein (KK) excitations of Standard Model particles are essentially degenerate. Radiative corrections will, however, lift this degeneracy, allowing the first level excitations to decay to the lightest KK particle (LKP), which is the gamma^*. KK number conservation implies that the LKP is stable. Then, since the SM particles radiated during these decays are rather soft, the observation of KK excitations production and decay in collider experiments will be quite difficult. We propose to add to this model KK number violating interactions mediated by gravity, which allow the gamma^* to decay to a photon and a KK graviton. For a variety a models and a large range of parameters, these decays will occur within the detector. Thus, pair production of KK excitations will give rise to a striking collider signal, consisting of two hard photons plus large missing energy (due to escaping gravitons). We evaluate the cross-section for these signals at the Tevatron and LHC, and derive the reach of these colliders in the search for universal extra dimensions.