The purely rotational microwave spectrum of HCN and DCN embedded in He-4 nanodroplets has been measured. The J=0-->1 transitions for both molecules have been recorded at 72.21 and 59.90 GHz, respectively. The increase in moment of inertia due to the presence of liquid helium, which the assumption of adiabatic following of the helium density predicts should be almost identical for both molecules, is found to be 9% smaller for the faster of the two rotors, HCN. This result is interpreted as a breakdown of the adiabatic following approximation, which is valid for the slower rotors. Power-saturation measurements have also been performed, and show that the rotational relaxation time for these molecules is on the order of 10(-8) s.