Does the wavelength always decrease in a medium? I was studying a GRE Physics Test problem where optical light with a wavelength of 500 nm travels through a gas with refractive index $n$.
If we look at the equations for wave motion and index of refraction
$$c=\lambda_0\nu\quad\text{(in vacuum)}$$
$$v = \lambda\nu\quad\text{(in medium)}$$
$$n = c/v$$
we see that, if the frequency is constant, the wavelength decreases in the medium compared to vacuum. Is this a consistent property at all frequencies and for all mediums with refractive index real and greater than 1?
Are there dielectrics which change the frequency (still for n > 1), and is there an example of that?
 A: The index of refraction of a material can be less than 1 at high frequency, this is called "anomalous dispersion" and it happens as you cross an energy level of certain materials. It means that the phase velocity of light of a certain frequency is higher than c.
If the index of refraction is constant, as it is for long wavelengths, n has to be bigger than 1 to avoid superlumimal communication.
The principle of energy conservation in a static environment forbids a frequency shift for a photon, since this would add energy or take away energy, and nothing in the medium is changing with the right frequency to do that. But light entering a moving medium shifts frequency. photons can combine to make one of double the frequency in a strong light beam in a nonlinear medium, and this corresponds to making higher harmonics of the classical field. 
A: As for your second question, dielectrics which change the frequency, any medium which changes the frequency must be a nonlinear medium.  There are many of them.  They do not change the frequency continuously, but rather they generate higher order harmonics, an integral number times the original frequency.  
A: The answer to your first question 

Is this a consistent property at all frequencies and for all mediums with refractive index real and greater than 1?

is Yes. 
Not only in optics but in other wave mechanics too.

Refraction of light is the most commonly observed phenomenon, but any type of wave can refract when it interacts with a medium, for example when sound waves pass from one medium into another or when water waves move into water of a different depth

