Kevin
The only thing I can think of is an issue with the GD2 color libraries on the server? Please tell you if you have any supporting information other then what I am finding.
Here is my test
Imagemagick and watermark flawless
IMG_58871 - ReefTalk Gallery
GD2 with and without watermark
IMG_588711 - ReefTalk Gallery IMG_588712 - ReefTalk Gallery
Both to me are of less quality than Imagemagick. In fact I think both with and without watermarking are of the same lesser quality
Now I use 100% for images so I dont think there is an issue here. In fact the only PHP GD2 command which accepts any kind of quality setting is ImageJPEG and we do input a quality there. Thus I process that file using GD2 with or without a watermark on my server you can see there is definate color degrading using GD2.
Given that this degredation is happens regardless of watermark or no watermark as shown in my testing and also to the fact that all the image processing strings this might either be a limitation on GD2 and color sampling or the version on the servers color libraries.