One solution could be to use several points for each label (color name). For instance, we could use a limited set of color names (red, green, blue, etc) but have a lot of points associated to this labels. For example, different points like #07250b (that is, in my opinion, missclassified) and #51f665 could share a same label: green. The main problem is that I'm not sure It is possible to find such a dataset on the internet. Maybe we can build one from sites like http://cloford.com/resources/colours/500col.htm, removing the numbers from each color name.

With several points for each label, It will give us the possibility of using a 3NN, for example, instead of a 1NN classifier. It should impact also on the results, but I'm not sure it will really improve the results.