@IndischerPhysiker has already answered the question, but I would like to bring forward an example of Cherenkov radiation - a phenomenon that occurs when a particle moves through the medium faster than the speed of light (in the medium), and raises precisely the question voiced in the OP:
Cherenkov radiation is electromagnetic radiation emitted when a charged particle (such as an electron) passes through a dielectric medium at a speed greater than the phase velocity (speed of propagation of a wave in a medium) of light in that medium. Special relativity is not violated since light travels slower in materials with refractive index greater than one, and it is the speed of light in vacuum which cannot be exceeded (or reached) by particles with mass.
Update
The way I would answer the question is: the speed of interactions is invariant. In vacuum the speed of light (i.e., the product of the wavelength and the frequency) is the same as the speed of interactions, but not in a medium, because the medium responds to the fields of the electromagnetic wave. But the speed of interaction, e.g., between the wave and the medium is still the speed of light in vacuum. This appears paradoxical only when we treat the medium as continuous, whereas on microscopic level we are still in vacuum. Indeed, refractive index is but a simplification for describing the field that is a superposition of the original light wave and the polarization and magnetization induced by this wave in the environment:
$$
\mathbf{E} = \frac{1}{\epsilon_0}\left(\mathbf{D}-\mathbf{P}\right),\\
\mathbf{B} = \mu_0\left(\mathbf{H}+\mathbf{M}\right).
$$
A related issue is the difference between the phase velocity, $v_{ph}=\lambda\nu=\omega/k$ and the group velocity, $v_g=\partial \omega(k)/\partial$ - the phase velocity can exceed the speed of light in vacuum, but the group velocity cannot - it is the latter that corresponds the the speed with which information propagates. In vacuum or dispersionless medium $\omega(k)=ck$ and the two velocities coinside.