Alright, instead of separating the picture by graylevels, I tried to get more involved with component detections.
I noticed the original painting has a different color for hair, face, mouth, eyes, and clothes. I tried my best to replicate this.
i = ImageCrop[Import["http://s2.hubimg.com/u/4262573_f520.jpg"]];
id = ImageDimensions[i];
back := Image[RandomColor[], ImageSize -> id];
bw = ChanVeseBinarize[i, Binarize[GradientFilter[i, 1], .05]] //
ColorNegate;
ib = ColorConvert[
RemoveAlphaChannel[
RemoveBackground[i, {"Background", {"Uniform", 0.1}}],
Darker[Gray, 1]], "Grayscale"];
noback = DeleteSmallComponents[ChanVeseBinarize[ib, EdgeDetect[ib]]];
face = Round[FindFaces[bw]][[1]];
facemask =
Rasterize[
Style[Show[{SetAlphaChannel[bw, 0],
Graphics[{Black, Disk[Mean[face], (Mean[face]/2)*{1, 1.4}]},
Background -> Transparent]}], Antialiasing -> False]];
facemask = SetAlphaChannel[facemask, facemask // ColorNegate];
facemaskc :=
ColorReplace[facemask,
Black -> RandomColor[Hue[_, _, RandomReal[{.6, 1}]]]];
mouth = ImageTake[
DeleteSmallComponents[
RemoveAlphaChannel[
RemoveBackground[
ImagePad[ImageTrim[bw, face], {{0, 0}, {0, 10}}, Black]],
White] // ColorNegate] // ColorNegate, {11, -1}];
mouth = ImagePad[
RemoveAlphaChannel[
ColorConvert[
SetAlphaChannel[mouth,
ColorNegate[
Dilation[Closing[ColorNegate[mouth], 30],
DiskMatrix[{2, 5}]]]], "RGB"],
Black], {{face[[1, 1]], id[[1]] - face[[2, 1]]}, {face[[1, 2]],
id[[2]] - face[[2, 2]]}}, White];
mouthc :=
ColorReplace[
SetAlphaChannel[mouth, Binarize[mouth, .9999] // ColorNegate],
Black -> RandomColor[]];
Rasterize[
Overlay[{noback,
SetAlphaChannel[Binarize[facemask], Binarize[facemask]]}]];
ImageAdd[#, DeleteSmallComponents[# // ColorNegate]] &[%];
eyesNose =
DeleteSmallComponents[Opening[%, 2] // ColorNegate] // ColorNegate;
lines = ImageLines[EdgeDetect[eyesNose], MaxFeatures -> 1][[1]];
eyes = SelectComponents[ColorNegate[eyesNose], "Centroid",
Abs[#[[2]] - Mean[lines[[All, 2]]]] < 20 &] // ColorNegate;
eyes = ImageTake[
ImagePad[
RemoveAlphaChannel[
ColorConvert[
SetAlphaChannel[eyes,
ColorNegate[
Dilation[Closing[ColorNegate[eyes], 10],
DiskMatrix[{2, 7}]]]], "RGB"], Black], {{0, 0}, {7, 0}},
White], {8, -1}];
eyesc := ColorReplace[
SetAlphaChannel[eyes, Binarize[eyes] // ColorNegate],
Black -> RandomColor[]];
SetAlphaChannel[ColorConvert[noback, "RGB"], noback];
hair = ImageTake[%, id[[2]] - face[[1, 2]] + 1];
torso = ImageTake[%%, -face[[1, 2]] + 1];
hairTorso :=
ImageAssemble[
Map[ColorReplace[#,
White -> RandomColor[]] &, {{hair}, {torso}}, {2}]];
composition :=
Rasterize[
Overlay[{back,
ImageCompose[hairTorso, ImageCompose[facemaskc, ImageCompose[eyesc,
ImageCompose[mouthc,
SetAlphaChannel[
ColorReplace[bw,
Black -> RandomColor[Hue[_, _, RandomReal[{.05, .5}]]]],
bw // ColorNegate]]]]]}]]
GraphicsGrid[Partition[Table[composition, {8}], 4], ImageSize -> 800]

I'm quite pleased with the result, but the code got kind of long and I'm sure it could be optimiesd.