this can easily happen when

you use a wrong color scheme

save with insufficient bit depth

use filters/effects on the whole tileset (like changing brightness or stuff) - only perform these operations on single tiles!

your tool is crap and doesn't care about keeping the original RGB values

you use a compressed format like JPG or GIF which will fuck up all the RGB values