The Kaluza-Klein (KK) decomposition of higher-dimensional gravity gives rise to a tower of KK-gravitons in the effective four-dimensional (4D) theory. Such massive spin-2 fields are known to be connected with unitarity issues and easily lead to a breakdown of the effective theory well below the naive scale of the interaction. However, the breakdown of the effective 4D theory is expected to be controlled by the parameters of the 5D theory. Working in a simplified Randall-Sundrum model we study the matrix elements for matter annihilations into massive gravitons. We find that truncating the KK-tower leads to an early breakdown of perturbative unitarity. However, by considering the full tower we obtain a set of sum rules for the couplings between the different KK-fields that restore unitarity up to the scale of the 5D theory. We prove analytically that these are fulfilled in the model under consideration and present numerical tests of their convergence. This work complements earlier studies that focused on graviton self-interactions and yields additional sum rules that are required if matter fields are incorporated into warped extra-dimensions.