Experimental evidence from both spin-valve and quantum transport measurements points towards unexpectedly fast spin relaxation in graphene. We report magnetotransport studies of epitaxial graphene on SiC in a vector magnetic field showing that spin relaxation, detected using weak-localization analysis, is suppressed by an in-plane magnetic field B∥, and thereby proving that it is caused at least in part by spinful scatterers. A nonmonotonic dependence of the effective decoherence rate on B∥ reveals the intricate role of the scatterers’ spin dynamics in forming the interference correction to the conductivity, an effect that has gone unnoticed in earlier weak localization studies.