We report measurements of the nuclear spin-lattice and spin-spin relaxation times of very dilute 3He in solid 4He in the temperature range 0.01 leq T leq 0.5 K for densities where anomalies have been observed in torsional oscillator and shear modulus measurements. We compare the results with the values of the relaxation times reported by other observers for higher concentrations and the theory of Landesman that takes into account the elastic properties of the 4He lattice. A sharp increase in the magnitude of the nuclear spin-lattice relaxation times compared to the the classical Landesman theory is observed close to the temperatures where the torsional and shear modulus anomalies are observed. The NMR results suggest that the tunneling of 3He impurities in the atomic-scale elastic distortion is affected by the same processes that give rise to the macroscopic elastic dissipation anomalies.