I don't know how you're doing the palette extraction right now, but if want something to experiment with I'd suggest you take a look at using k-means clustering. In other words see the set of pixels as points in a 3D space (where the axes are red, green and blue) and then perform k-means clustering on the points. You could then extract the palette from the centroids. If k-means doesn't give satisfactory results, try spectral clustering.