The temperature dependence of the electron-spin relaxation time in MgB2 is anomalous as it does not follow the resistivity above 150 K; it has a maximum around 400 K and decreases for higher temperatures. This violates the well established Elliot-Yafet theory of spin relaxation in metals. The anomaly occurs when the quasiparticle scattering rate (in energy units) is comparable to the energy difference between the conduction and a neighboring bands. The anomalous behavior is related to the unique band structure of MgB2 and the large electron-phonon coupling. The saturating spin relaxation is the spin transport analogue of the Ioffe-Regel criterion of electron transport.