The dynamics of 3He atoms in solid 4He have been investigated by measuring the NMR relaxation times T1, T2 in the region where a significant non-classical rotational inertia fraction (NCRIF) has been reported. For 3He concentrations x3 = 16 ppm and 24 ppm, changes are observed for both the spin-lattice relaxation time T1 and the spin-spin relaxation time T2 at the temperatures corresponding to the onset of NCRIF and, at lower temperatures, to the 3He-4He phase separation. The magnitudes of T1 and T2 at temperatures above the phase separation agree roughly with existing theory based on the tunneling of 3He impurities in the elastic strain field due to isotopic mismatch. However, a distinct peak in T1 and a less well-resolved feature in T2 are observed near the reported NCRIF onset temperature, in contrast to the temperature-independent relaxation times predicted by the tunneling theory.