Have you considered using fine art as training data, perhaps broken down into movements/motifs? In your blog posts you mentioned that not all photographs make for well chosen palettes, this could get around that as artists should have a great understanding of theory.
As far as the pixel-level errors in your palette training, would downscaling+blur solve this?