We investigate cross-relaxation interactions between Tm and Al in Tm:YAG using two optical methods: spectral holeburning and stimulated echoes. These interactions lead to a reduction in the hyperfine lifetime at magnetic fields that bring the Tm hyperfine transition into resonance with an Al transition. We develop models for measured echo decay curves and holeburning spectra near a resonance, which are used to show that the Tm-Al interaction has a resonance width of 10~kHz and reduces the hyperfine lifetime to 0.5 ms. The antihole structure is consistent with an interaction dominated by the Al nearest neighbors at 3.0 Angstroms, with some contribution from the next nearest neighbors at 3.6 Angstroms.