Spin relaxation due to atom\char21{}atom collisions is measured for magnetically trapped erbium and thulium atoms at a temperature near 500 mK. The rate constants for Er\char21{}Er and Tm\char21{}Tm collisions are $3.0\ifmmode\times\else\texttimes\fi{}{10}^{\ensuremath{-}10}$ and $1.1\ifmmode\times\else\texttimes\fi{}{10}^{\ensuremath{-}10}$ cm${}^{3}$ ${\mathrm{s}}^{\ensuremath{-}1}$, respectively, $2\char21{}3$ orders of magnitude larger than those observed for highly magnetic $S$-state atoms. This is strong evidence for an additional, dominant, spin relaxation mechanism, electronic interaction anisotropy, in collisions between these ``submerged-shell,’’ $L\ensuremath{\ne}0$ atoms. These large spin relaxation rates imply that evaporative cooling of these atoms in a magnetic trap will be highly inefficient.