I think you're working in 8-bit mode (256 color) which has a very limited palette. Change it up to RGB (or 24-bit mode), do your work, and then save it back down to 8-bit when you're done.
If you have options for diffusion dithering when you save it back down, I'd recommend using it.