Yes it is about color usage.
Have you noted that there's a HUGE value jump from the saturated purple to the first flesh shade? If you grayscale it it's a huge jump, it's even huger in how the purple is saturated (makes it warmer and needs more buffer shades before it can mesh with the flesh shades that are relatively desaturated. Blur your eyes a little and look at your palette ramp. Tell me if after the blue in the middle, the rest of the shades don't blur out to a single color more or less. This isn't bad Subtlety makes for index swapping and good dithering and shit. But you need more shades to go from the dark 1/3rd of the palette to the bright 2/3s of it. Keep in mind, you don't need many dark shades because in darkness there isn't much detail, it all blends towards a single color, that's fine. So it's good you have more palette slots for brighter stuff. But what you're missing, is MIDDLE VALUE RANGE. In a big way.
That is all for now. Remember, portray volumes before you start dithering and AAing.