This question nagged me for most of Friday. It seems obvious that it is a Goldstone mode. You can translate the ICDW and the energy does not chage. However it is not clear what continuous symmetry remains since the lattice has already broken translation symmetry. To get to the bottom of the issue we should focus on the relevant Hamiltonian which is electron+phonon
$$
H=\sum_k\epsilon_k c_k^\dagger c_k+\sum_q\hbar\omega_q b_q^\dagger b_q+\sum_{k,q}g(k)c_{k+q}^\dagger c_kb_q+h.c.
$$
where $c_k^\dagger$ and $b_q^\dagger$ are electron and phonon creation operators respectively and $h.c.$ denotes Hermitian conjugate of the interaction term. This Hamiltonian is invariant under the continuous transformation
$$
c_k\to c_k e^{ika\varphi} \\
b_q\to b_q e^{iqa\varphi}
$$
for any choice of $\varphi$, and $a$ is the lattice constant. To see this is the relevant phase for CDW consider a simple 1D system with Peierls transition. There the CDW causes phonons to condense and the complex order parameter $\Delta$ is
$$
\Delta=|\Delta| e^{i\varphi}=g(2k_f)\langle b_{2k_f}+b_{-2k_f}^\dagger\rangle.
$$
The phase of $\Delta$ is chosen by spontaneous symmetry breaking with $\varphi$ parameterizing the continuous symmetry so there is a goldstone mode. For completeness the charge density is
$$
\rho_0+\delta\rho\cos(2k_f x+\varphi).
$$
The CDW order parameter I got from this reference.
Upon initial inspection the continuous symmetry here appears to be ordinary translation invariance ($\psi_k\to \psi_k e^{ikr}$). This cannot be correct as translation symmetry was already broken in forming the lattice and phonons. The continuous symmetry that $H$ posses is a $U(1)$ symmetry that is a remnant of the full translation symmetry $\mathbb{R}=\mathbb{Z}\times U(1)$. The $U(1)$ component of $\mathbb{R}$ is a translation symmetry with translation only defined within a unit cell of the lattice. Translation by multiple unit cells comes from the $\mathbb{Z}$ factor of $\mathbb{R}$.
In systems that break continuous translation symmetry (regular crystals,lamellar solids, smectics etc.) one also necessarily breaks rotational invariance (but note that this is not true the other way around, allowing liquid crystals to exist). As you rightly pointed out the simple goldstone mode count does not seem to work in such ordered phases.
The reason is essentially because the orientational degrees of freedom get slaved to the translational phonon modes, which results in the orientational modes no longer being soft (they get gapped) and hence not Goldstone modes. This is analogous to the Anderson-Higgs mechanism but is different in that we only have global symmetries being spontaneously broken and no gauge fields involved in forming a crystal.
To see it explicitly, we can take for example a regular 3d crystal (with reciprocal lattice vectors ${\bf G}_n$). Then the relevant non-vanishing order parameter is going to be the fourier component of the mass density
$$
\rho({\bf r})=\rho_0+\sum_{{\bf G}_n}\left[\psi_{n}e^{i{\bf G}_n\cdot{\bf r}}+\mathrm{c.c}\right]
$$
where $\rho_0$ is the mean density and $\psi_n$ are the complex fourier amplitudes ($\langle|\psi_n|\rangle\neq0$ in the crystal). As the energy is invariant under uniform translations we require ${\bf r}\rightarrow{\bf r}+{\bf u}\implies\psi_n\rightarrow\psi_n e^{-i{\bf G}_n\cdot{\bf u}}$.
Now a global rigid rotation is also a symmetry of the energy: ${\bf G}_n\rightarrow{\bf G}_n+\delta\theta\times{\bf G}_n$. This leads to a corresponding displacement of lattice points as ${\bf u}=\delta\theta\times{\bf r}$.
As ${\bf u}$ is the translational goldstone mode and $\delta\theta$ is the rotational one, we immediately see that the orientational zero modes are slaved to the translation phonon modes ($\bf u$), which in this particular case is specified by
$$
\delta\theta_i=\dfrac{1}{4}\epsilon_{ijk}(\partial_j u_k-\partial_k u_j)
$$
which is the antisymmetric part of the strain tensor. As $u_i$ is a goldstone mode, its two point correlator will have a pole at zero wave-vector (momentum). This can also be obtained using linear classical elasticity for the phonons. Therefore heuristically (being cavalier about indices) as $\delta\theta\sim\partial u$ and $\langle|u(q)|^2\rangle\sim1/q^2$, we have $\langle|\delta\theta(q)|^2\rangle=$const. as $q\rightarrow0$ showing that the orientaional modes are no longer soft but are instead gapped (even though the rotational symmetry was spontaneously broken). This point was already noted by Mermin (Phys. Rev. 176, 250 (1968)) as it leads to true long-ranged orientational order even in 2d crystals.
You can also look at the book "Principles of Condensed Matter Physics" by Chaikin and Lubensky, where this point is discussed in multiple cases (including for the smectic-A phase, in which case a generalization of this point leads to the spectacular analogy between the SmA-Nematic transition to that of a superconductor).
Best Answer
An ordered SDW phase breaks both the continuous $SU(2)$ spin-rotation symmetry and the time-reversal symmetry (because the presence of either of these two symmetries would force the order parameter of SDW vanishing). It is the spontaneously broken of continuous spin-rotation symmetry that leads to the gapless Goldstone mode. Here is a related issue.
The Goldstone mode of SDW is a gapless excitation of spin system, which is similar to that of phonons (the elementary excitations of oscillating crystals).