Great effort, this is how I'd change your palette.

The characters firstly need a bit more contrast in the colours, the lightest is now white..
With the hue shifts its probably best to be a bit more obviously with such small characters, exagerate the shifts, but still use your instict, alter the contrast, saturation of your colours.. no one picks a perfect palette, it's just trying to get the most out of the colours after all.