I suggest you avoid trying to get a neat 'ramp' and instead accept pairs of similar-brightness, different-hue. Also because of the nature of the source material, and of paintings in general, it doesn't necessarily work very well to pick a set of colors for an individual object but rather I think picking colors for the entire piece is required.
Hence, here is my suggestion for a palette to try:
I approached this as a color-segmentation problem: picking a palette that would produce the most contiguous, readable shapes from the source material after indexization. So I grabbed the pencil tool with a large tip, eyedropped some colors
and laid out sample blobs on top of the painting (in a separate layer). I tried to pick representative colors -- colors that there was relatively a lot of. There's definitely an art to eyedropping from the right place, but once you know it it should be pretty easy to make your own palettes without eyedropping.
I imported the new layer as a palette, decided that the hair colors were needed for coherence and a stronger pink was needed, eyedropped them and added them into the palette.
The result is 16 colors (for the entire painting, not the skin -- there is too much ramp overlap in paintings to
have really distinct ramps)
I believe that in the case of paintings, pure grays and medium-saturation colors are used as utility colors, with high-saturation making up 'spot colors' and pastels comprising the mess of colors that provide more subtle definition.
EDIT:
For working out a decent palette, cutting out the object of interest and indexizing it with a good algorithym (eg. GIMP does a good job) usually gives good results (not necessarily optimal -- most palette optimization algorithyms tend to reduce extreme values, so it's better to ask the paintprogram for a set of say 6 colors which will accurately reflect the gist of the source area, then fill in the inbetween colors yourself. Running Unsharp Mask beforehand with a high radius (16.5 in this case) to counteract the reduction of color extremities is fairly effective.
Miascugh's entry in the thread mathias links seems to get the sort of results you might want.
Hope some of that helps