We present the first femtosecond studies of electron-phonon (e-ph) thermalization in heavy-fermion compounds. The e-ph thermalization time tau(ep) increases below the Kondo temperature by more than 2 orders of magnitude as T=0 K is approached. Analysis using the two-temperature model and numerical simulations based on Boltzmann's equations suggest that this anomalous slowing down of the e-ph thermalization derives from the large electronic specific heat and the suppression of scattering between heavy electrons and phonons.