Nuclear spin relaxation induced by hyperfine coupling is studied theoretically at positive and negative submicrokelvin temperatures. By avoiding the assumption of the high-temperature limit, adopted in conventional theories, we derive a formula in which the relaxation rate is expressed in terms of thermal averages of nuclear spin energies. The exchange interaction induces an asymmetry in the energy spectrum, which leads to relaxation rates that depend on whether the nuclear spin temperature is positive or negative. High-temperature expansion methods and Monte Carlo simulations are applied to explain the anomalous results by Hakonen et al. in rhodium qualitatively.