Some good points have been made.
I think that if I were to approach these, I would first work on giving the characters
identifiable silhouettes. Without deviating from the acceptable character proportions of the style, this can be done by varying height, jawline, ear size, and exaggerating hair styles, accessories, and clothing. When doing so, keeping an awareness of negative space is important as well.
Here, we have a morph between the silhouettes of your portraits and the adjustments I made:
To further illustrate the variety of silhouettes within each group, I've overlaid the silhouettes atop each other:
Note the strong, Charlie-Brown-esque commonality in the original ones, but the more amorphic shape of the new set.
Now, assuming that there are no other palette restrictions, and that all colors could be used freely within the portraits, I'd suggest using red within the faces as well to increase variation. I also really don't think the large, round, uniform eyes are working at this resolution and with this style.
To show more face possibilities, I've made two combinations for each character. If not restricted otherwise (like all characters being represented by the same tiny gameplay sprite elsewhere), you could also vary the clothing by inverting red/white (as I did for two in the bottom row). Also, greater variation in stance and facial expressions (slightly hunched shoulders, hands in pockets, arms at side or seemingly extending outward) can imply more about unique personalities, causing the images to look less like ID photos.
Finally, breaking symmetry in one or two ways per portrait, for visual interest, is key too. An offset smile or beauty mark (mole) could be used alongside the cross strap or headband bow as well. In fact, looking back at NESrocks' attempt, I think he has the right idea in giving one of the characters an asymmetrical hair part, and that two styles of pig tails in mine would be too common.