I would first convert from a background layer to a regular layer, as mentioned above.
In the screen capture below, I used replace color, but there’s more than one way to go abou tit.
(A quirk of the Sonic image you linked is that it has two near identical blues.)
If you check the properties of the image, you’ll see the bit depth. The sonic sprite sheet is originally 24 bits – meaning 8 bits per 3 channels RGB. No alpha. After converting the background to a regular layer and re-saving, it’s 32 bits, for RGBA.
Edit: As you can see, I’m on Windows. If you notice anything different about the process in Linux, then maybe that’s part of the issue.
Basically the opposite of this:
If you change the image’s color mode to indexed, then save to a file format that supports indexed, its bit depth will be 8. Indexed color images reference palette indices in the range [0, 255].
app.command.OpenFile()
app.command.LayerFromBackground()
A script might be able to automate this for you. As usual, there’s more than one way to accomplish that – with commands and without.