Such a big sprite would never be one with the backround, and yeah, you could use black really. But the next shade from black should be about 30 lightness or something.
Can't you see that in both of the palette swaps you posted, the shade next to the darkest shade doesn't ramp smoothly into the next lightest one? Too big a jump, too close to black, too saturated.
Do take a look at the knee I edited also.
