The black is fine, its dark, but the next shade up is quite a bit brighter and thus creates a contrast imbalance. Everything except for the black needs to be readjusted.
I made a quick and dirty contrast rebalanced. Try to adjust it somewhat like this.
I originally didn't see what you were referring too, but have since discovered that the woman who owns the computer I'm using in fact had the brightness and contrast settings much lower then they should be. I've readjusted and do somewhat see the problem, even if to differentiate the dark shade and the "black" shade was part of the point (to allow for more differntiation between Shanoa's hair and her figure).
Despite that however, I find that your alteration appears near identical to how the peice used to look on the old settings. I'll alter the "official" palette sometime soon, when I've actually got the time to do so, along with playing around with the shading a bit more.