When you do save for web are you choosing GIF? If so what color palette is selected.
GIF is 256 colors only so your colors may shift. The program remaps your colors to that 256 color palette. However you have control over how that palette is made. Adaptive is the best for accuracy. Adaptive builds the 256 color palette based off the colors in your image. You'll get the least amout of color shift with this one. Selective and one or two others are ok (find the best color shift and file size combo. The websafe palette is the worst.
I never chose websafe anymore as it is a total joke these days (it can be useful if you just want to narrow down your color choices when building files though). It came out years ago when everyone had video cards that only showed thousands of colors or so, and only 216 colors were common among all video cards and operating system. Today, with 17.6 million colors or so, a palette far beyond what what the human eye can differientiate betweeen, can anyone honeslty say that only 216 colors are common amongst all cards. I think not. Anyhow, I've said my peace.
If you are choosing JPEG, then I am not sure what the issue is.
Sorry if this is all "well duh" material, lol. I just offered my guess in case it helps.