The effect you're going for is less of a pure hue shift and looks more like old-school palette shifting effect. On old hardware this was implemented by arranging the color palette used for the image such that there was a run of similar colors (for example, a series of blues increasing in saturation, in the case of your first image) and then shifting and rotating the values in that palette by one (modulo the palette size).
Most modern hardware does not support palette images or rendering.
However, you can simulate the effect fairly easily by creating a 1D texture that contains the range of colors you'd like to cycle through. This will serve as your palette. You'll also want a texture that represents which part of that palette to sample for any given fragment being rendered. This index texture is essentially a grayscale version of your sprite.
Each texel in the index texture/sprite is actually a texture coordinate that looks up a position in the 1D palette texture. In your shader, simply read the index texture and use that result to look up into the color palette texture:
// Since the index is grayscale, you only need to deal with one
// component of the resulting color.
float index = texture2d(textureCoordinates, yourIndexTextureSampler).r;
vec4 color = texture1D(index + shiftUniform, yourPaletteTextureSampler);
...
The gray values in the index texture should be based on the number of colors in your palette. Let's say you have eight values in your palette and your index texture uses 8 bits per component. You'd use colors like the following in your index image:
0, 0, 0 palette entry 0
32, 32, 32 palette entry 1
64, 64, 64 palette entry 2
...
All you're doing here is dividing up the color space in the index image into eight discrete buckets so that when you feed that color (which the hardware will turn into value between 0 and 1 for you) back into the dependent texture read for the color texture you'll get the appropriate color (because that texture is also broken up into eight discrete chunks, one for each color in the palette).
That will give you a basic approximation of palette-based rendering. To implement shifting, simply add a uniform that represents the shift (which varies over time) and add that to the sampled index value, modulo the range of the palette. In the shader example above, there's no explicit modulo operation because texture address wrapping can take care of it for you.
