Femtosecond x-ray magnetic circular dichroism was used to study the time-dependent magnetic moment of 4f electrons in the ferromagnets Gd and Tb, which are known for their different spin-lattice coupling. We observe a two-step demagnetization with an ultrafast demagnetization time of 750 fs identical for both systems and slower times which differ sizeably with 40 ps for Gd and 8 ps for Tb. We conclude that spin-lattice coupling in the electronically excited state is enhanced up to 50 times compared to equilibrium.