Models of Universal Extra Dimensions (UED) at the TeV scale lead to the presence of Kaluza Klein (KK) excitations of the ordinary fermions and bosons of the Standard Model that may be observed at hadron and lepton colliders. A conserved discrete symmetry, KK-parity, ensures the stability of the lightest KK particle (LKP), which, if neutral, becomes a good dark matter particle. It has been recently shown that for a certain range of masses of the LKP a relic density consistent with the experimentally observed one may be obtained. These works, however, ignore the impact of KK graviton production at early times. Whether the G^1 is the LKP or not, the G^n tower thus produced can decay to the LKP, and depending on the reheating temperature, may lead to a modification of the relic density. In this article, we show that this effect may lead to a relevant modification of the range of KK masses consistent with the observed relic density. Additionally, if evidence for UED is observed experimentally, we find a stringent upper limit on the reheating temperature depending on the mass of the LKP observed.