The problem is the error only accumulates on the red channel, and since
the channel is capped at 255, the black entry continues to match for the
entire image.
As a partial solution we can process the image as grayscale when the
supplied palette is grayscale.
This isn't a perfect solution, since the caller can still provide a
palette that doesn't cover the gamut used in the image, but it does
handle a common case.