Is your gallery up on the web?
Which version of Photoshop.
Go into the HTML for the gallery..
Look at the image tag for the picture.
<IMG SRC="./filename.jpg" width="xx" height="yy">
See if xx and yy are correct.
I have CS, it generates xx and yy to be wrong, one pixel less then the true width and height of the image. This causes the browser to rescale the image and make it look pretty rotten. It shouldn't effect color but it does tend to make them look not as sharp and have no "pop".
Go into the gallery tool and deselect the option to include the width and height in the image tags. Then the browser will just pick the actual size of the image and it will look fine.