The intergalactic medium is expected to be at its coldest point before the formation of the first stars in the universe. Motivated by recent results from the EDGES experiment, we revisit the standard calculation of the kinetic temperature of the neutral gas through this period. When the first ultraviolet (UV) sources turn on, photons redshift into the Lyman lines of neutral hydrogen and repeatedly scatter within the Lyman-$alpha$ line. They heat the gas via atomic recoils, and, through the Wouthuysen-Field effect, set the spin temperature of the 21-cm hyperfine (spin-flip) line of atomic hydrogen in competition with the resonant cosmic microwave background (CMB) photons. We show that the Lyman-$alpha$ photons also mediate energy transfer between the CMB photons and the thermal motions of the hydrogen atoms. In the absence of X-ray heating, this new mechanism is the major correction to the temperature of the adiabatically cooling gas ($sim 10 %$ at $z=17$), and is several times the size of the heating rate found in previous calculations. We also find that the effect is more dramatic in non-standard scenarios that either enhance the radio background above the CMB or invoke new physics to cool the gas in order to explain the EDGES results. The coupling with the radio background can reduce the depth of the 21-cm absorption feature by almost a factor of two relative to the case with no sources of heating, and prevent the feature from developing a flattened bottom. As an inevitable consequence of the UV background that generates the absorption feature, this heating should be accounted for in any theoretical prediction.