We show that the electron-phonon coupling in graphene, in contrast with the non-relativistic two-dimensional electron gas, leads to shifts in the phonon frequencies that are non-trivial functions of the electronic density. These shifts can be measured directly in Raman spectroscopy. We show that the frequency shift depends on the dynamical charge polarization function that vanishes at long wavelengths, indicating that frequency changes are only possible in the absence of translational invariance, i.e., in the presence of disorder. We show that depending on the value of the chemical potential relative to the phonon frequency, the frequency shift can positive (hardening) or negative (softening) relative to the neutral case (when the chemical potential is at the Dirac point). We show that the use of the static response function to calculate these shifts is incorrect and leads always to phonon softening. In samples with many layers, we find a shift proportional to the carrier concentration, and a splitting of the phonon frequencies if the charge is not homogeneously distributed. We also discuss the effects of edges in the problem.