And Evil shall reign o'er all.

[Hoeloe]

Ah, so it's the lack of contrast creating the issue. I seem to have misunderstood what was meant by a "dark palette", I thought that meant I needed to increase the brightness of all the colours, not boost the contrast. Seems I was in error.

I had a go at it. I noted that in the example sprite shown, there was a lot more black than I had in my sprite, so I increased the amount of that colour.