[chuckbot]

I like this solution much better, here is why:

k-means is not a mode seeking algorithm, I think. You are clustering your color space, but you're not even guaranteed to end up with colors that are very close to those in your image. With a high k you're getting actual colors in the image, but they're not really dominant anymore.

What about mean shift? It's based on one method of non-parametric density estimation. Another method is this: Some sort of histogramming, which is another method of non-parametric density estimation.

Also other colors spaces will pay off immensely.