We report on measurements of the spin lifetime of nuclear spins strongly coupled to a micromechanical cantilever as used in magnetic resonance force microscopy. We find that the rotating-frame correlation time of the statistical nuclear polarization is set by the magneto-mechanical noise originating from the thermal motion of the cantilever. Evidence is based on the effect of three parameters: (1) the magnetic field gradient (the coupling strength), (2) the Rabi frequency of the spins (the transition energy), and (3) the temperature of the low-frequency mechanical modes. Experimental results are compared to relaxation rates calculated from the spectral density of the magneto-mechanical noise.