I don't really have much to suggest, but do have some questions to try to better understand the situation.
1) What are you using as your image source? Are you GISing, and then copypasting from browser into PS? Or are you saving the file locally before opening it? Copypasting from an already local file to a new file?
2) Does it happen all the time with blues and greens? For instance, if you were to open a new 800x600 (or whatever) image, and fill it with a blue or green, would you experience this issue? Or only after you start editing?