Great idea. I feel like an alternate color model could help, because of all the places where the color is arbitrary but strong average to a muddy sepia.
For example, the stripe on the truck should be bright and saturated, but the actual color doesn't matter.
The HSV colour space could work if the difference between colours is calculated with some kind of circular arithmetic.
I think the more fundamental problem is that the program is trying to minimize error where error is defined as deviation in color from the original image. This means objects that can be many different colors but are always strong and saturated average to a brown, as you said. And as you said, for those types of objects, it's best to pick a random color and make it bright and saturated. The best way to have it do that is to redefine error as some metric of how "realistic" the picture looks vs the original. For example, a picture of a car recolored to look bright blue looks similarly "realistic" to the human eye as the original picture where the car is bright red. The deviation in color is high, but it still looks "good", so the error should be low. I have no idea how this metric would be calculated without humans evaluating the output manually, though.
For example, the stripe on the truck should be bright and saturated, but the actual color doesn't matter.
The HSV colour space could work if the difference between colours is calculated with some kind of circular arithmetic.