We study the bound states of the Kaluza-Klein (KK) excitations of quarks in certain models of universal extra dimensions. Such bound states may be detected at future lepton colliders in the cross section for the pair production of KK quarks near threshold. For typical values of model parameters, we find that "KK quarkonia" have widths in the 10-100 MeV range, and production cross sections of the order of a few picobarns for the lightest resonances. Two body decays of the constituent KK quarks lead to distinctive experimental signatures. We point out that such KK resonances may be discovered before any of the higher KK modes.