5 Colors, 850 bytes

6 Colors, 947 bytes

7 Colors, 986 bytes

8 Colors, 1,028 bytes

As you can see, five colors is unacceptable in the image above. By gradually increasing the number of colors, we see that eight is the minimum number that can be used. The file size is still quite small without sacrificing quaility.

Photoshop Liabilities

Adobe Photoshop is an indispensable program for making images on the Web. But for designers, it's less than ideal. Let me show you a problem. If you make a circle in which the most prominent color is a certain red (say, 205, 53, 47) and you reduce the colors using an adaptive color palette, Photoshop returns a palette in which that same color, which should be unchanged, has shifted to a very similar, but different, shade of red (in this case, 201, 55, 49). This occurs because Photoshop reduces colors from a 24-bit (8x8x8) color space to a 15-bit (5x5x5) color space before executing its Median Cut algorithm to find the best palette. After the reduction, the resulting 15-bit palette gets a few extra bits tacked on to show the final palette color as RGB. Those extra bits cause the color shift you detect, and the color shift causes a dithered area when displayed on a browser with only 256 colors.
The only colors not affected are the eight at the corners of the color cube. Every other color will experience some shift after adaptive color reduction in Photoshop. If you are in a pinch, you can open the color table and type in the real values. While this works, it's tedious and no one should have to do it.
I hope to see a solution from Adobe, in the form of a true-color export plug-in. For now, I use Equilibrium DeBabelizer to do my final color reductions., because DeBabelizer does not shift colors.
Finally, Photoshop doesn't let the user see the color palette while viewing the image. I've requested this feature over and over, but Adobe doesn't have time to do it.