I know the problem seems to be solved, but for future reference, was the image originally a JPEG (I'm assuming it was) and if so, was it saved out of Photoshop 6 or better? And, if that's the case, then was it saved at it's best quality level (12)? I've found that images saved at 12 seem to display badly online (like browsers haven't caught up with decoding that kind of compression yet).
Another option might be if it's saved as CYMK and not RGB (I've had trouble with that as well).
Just thinking out loud.