Damping of coherent phonons at Gd(0001) and Tb(0001) surfaces is investigated by optical femtosecond time-resolved second harmonic generation. At low temperatures the damping rate increases monotonous with temperature. Close to the Curie temperature thephonon damping rate features an anomalous decrease, which is more pronounced for Tb than for Gd. This systematic variation is based on the difference in orbital momentum of the elements and identifies phonon-magnon scattering as the origin of the anomaly.