The tail of an aircraft that is rotating in pitch sees a change in apparent incidence relative to flying at a constant pitch angle. The resulting change in tail lift acts to oppose the rotation and is the main contribution to pitch damping. The magnitude of this rotation-induced incidence change is inversely proportional to TAS. So, using John's example, the same pitch rate at 40,000 ft will cause a change in airflow angle at the tail roughly half of that at the same IAS/EAS at sea level, halving the associated damping.
The same principles apply to the damping contributions of the fin due to yaw rate and the wing due to roll rate.