Employing analytical methods and quantum transport simulations we investigate the relaxation of quasiparticle spins in graphene proximitized by an s-wave superconductor in the presence of resonant magnetic and spin-orbit active impurities. Off resonance, the relaxation increases with decreasing temperature when electrons scatter off magnetic impurities-the Hebel-Slichter effect-and decreases when impurities have spin-orbit coupling. This distinct temperature dependence (not present in the normal state) uniquely discriminates between the two scattering mechanisms. However, we show that the Hebel-Slichter picture breaks down at resonances. The emergence of Yu-Shiba-Rusinov bound states within the superconducting gap redistributes the spectral weight away from magnetic resonances. The result is opposite to the Hebel-Slichter expectation: the spin relaxation decreases with decreasing temperature. Our findings hold for generic s-wave superconductors with resonant magnetic impurities, but also, as we show, for resonant magnetic Josephson junctions.