Like I said, applying a universal color reduction algorithm to a whole image like that pretty much never turns out well, even if you have more colors to work with. And then you have some additional console limitations on top of that, like how you can only use so many colors per tile, which probably confounds the problem even further.
If you want a good result you need to put manual work in to isolate and selectively optimize separate elements of the picture. I'm guessing this is probably what Rare did for the DKC title image.
I also think it's more or less crafted by hand. The better color quantizer
algorithms were develop from the 1990 onward, way after the median-cut color
quantizer (which was used most often for almost everything) was develop
(around 1985).
Unfortunately, the median-cut produces bad results when there are highlights
(few yet important colors) in the image, which is the case for many games. The
median-cut was (more or less) develop to quantize natural images, but does a
bad job for computer generated ones. Perhaps Rare had one of the better
quantizers at hand. Can't say. Anyhow. The better ones were computationally
quite expensive back than and required huge amounts of RAM. And the really
good ones were kept (and are kept) a good secret. I recently wrote an
improvement to the median-cut and an entire new color quantizer which rivals
and surpasses Photoshop's in some departments. My algorithm is able to account
for the highlights (specular components etc.) in an image and produces as such
far better results than Photoshop within this regard. However, this is 2016.