that original image you posted it is not a 16 color 4bit image - it is 24bit colour

if you posted up a 4bit image it may be that forum converted it and you can try reposting a zipped image

if you are happy to have the color palette reduced to 4bit in photoshop, I can do that before I recolor, but a 4bit image source would be better