We explore the phenomenology of Kaluza-Klein (KK) dark matter in very general models with universal extra dimensions (UEDs), emphasizing the complementarity between high-energy colliders and dark matter direct detection experiments. In models with relatively small mass splittings between the dark matter candidate and the rest of the (colored) spectrum, the collider sensitivity is diminished, but direct detection rates are enhanced. UEDs provide a natural framework for such mass degeneracies. We consider both 5-dimensional and 6-dimensional non-minimal UED models, and discuss the detection prospects for various KK dark matter candidates: the KK photon $gamma_1$, the KK $Z$-boson $Z_1$, the KK Higgs boson $H_1$ and the spinless KK photon $gamma_H$. We combine collider limits such as electroweak precision data and expected LHC reach, with cosmological constraints from WMAP, and the sensitivity of current or planned direct detection experiments. Allowing for general mass splittings, we show that neither colliders, nor direct detection experiments by themselves can explore all of the relevant KK dark matter parameter space. Nevertheless, they probe different parameter space regions, and the combination of the two types of constraints can be quite powerful. For example, in the case of $gamma_1$ in 5D UEDs the relevant parameter space will be almost completely covered by the combined LHC and direct detection sensitivities expected in the near future.