The TA2 phonon dispersion curves of Ni-Mn-Ga alloys with different compositions which transform to different martensitic structures have been measured over a broad temperature range covering both paramagnetic and ferromagnetic phases. The branches show an anomaly (dip) at a wave number that depends on the particular martensitic structure, and there is softening of these anomalous phonons with decreasing temperature. This softening is enhanced below the Curie point, as a consequence of spin-phonon coupling. This effect is stronger for systems with higher electronic concentration.