There is a fix for v1.3 using octrees for these cases where the image has more than 256 colors, but it’s not automatic by default (or not chosen automatically). Still thinking if it should be the default mode (it doesn’t work when the image has transparencies):
Probably it should be the default mode when there is no semi-transparent colors.