The low-frequency acoustic breathing modes in Au-Pb core-shell nanoparticles have been studied by time-resolved spectroscopy. The frequency of the breathing mode was determined for a series of samples with a 47 nm diameter Au core and Pb shells of different thickness. The measured frequencies decrease with increasing Pb content, but not to the extent expected from a classical model for a homogeneous sphere. These results show that the acoustic breathing modes of metallic core-shell particles are significantly perturbed when the two metals have different elastic properties.