すごく困ったのでメモしておく。
今までWindowsでしかもphotoshop6または７で作業することが多く、そのときはなかった現象。
mac(マック)で、photoshopCS3で「Web およびデバイス用に保存」する場合に、jpgでもgifでもpngでも色が変わってしまう。
黄みがかかった色や、グレー、紫の時はあまり気付かなかったが、青寄りの緑のデザインを「Web およびデバイス用に保存」で保存しようとすると、黄みの近い緑になってすごく困った。

解決策としては「Web およびデバイス用に保存」の画面で
Web 用に保存」画面の右側、「プリセット」の部分の「ICC プロファイル」にチェックがいれ、プレビュー右上にある、メニューボタンをプレスして、「ドキュメント内のプロファイルを使用」が選択する。（注：JPGの場合）

追記：2010/02/11
どこをどういじったのか、またしてもどんな色でも褪色してしまうようになって困った。
jpgに関しては上記の対処で解決するんだけど、gifに関しては「ICC プロファイル」の項目がないので、どうやっても褪色してしまう。
検索すると「編集」→「カラー設定」のところでカラー設定をいじるといいらしいのだけど、どういじっても同じ。
うーん。
悩んだ末に「編集」→「プロファイルの指定」で「作業用RGB:カラーLCD」に変更したことで解決。
ちなみに「カラー設定」は「作業用スペース」の「RGB」をカラーLCD、カラーマネジメントポリシーを「作業用RGBに変換」にしている。

追記：2010/05/26
相変わらず、定期的に悩んでる。何故なんだろう。
2010/02/11の設定でもgifがmacのfirefox及びsafariで褪色してしまう。
ちなみに検索すると、カラー設定、プロファイル設定ともにsRGBにするといいと書いてあるのだけど私の場合はそれでは直らない。

ちなみに「システム環境設定」の「ディスプレイ」の「カラー」は「カラーLCD」
他の設定にすると青くなるので、これ意外には設定できないぽい。

「編集」→「カラー設定」の作業用スペースのRGBはカラーLCD
カラーマネジメントポリシーのRGBは作業用RGBに変換
「編集」→「プロファイルの指定」でプロファイルをsRGB IEC61966-2.1
(2011/02/25注：「カラー設定」の作業用スペースはsRGBの方がよいでしょう。）

WEBおよびデバイス用に保存時、「ドキュメント内のプロファイルを使用」にチェック

で解決。

追記：2011/02/09
やっぱりgifの場合に、特にオレンジ色で彩度が低くなる、色が変わる現象がなおらない。
で、困っていたんだけれども
メニューからビュー→校正設定が作業用CMYKになっていて
これをモニタRGBに直したら解決しました。

追記：2011/02/25
illustratorデータをもらい、photoshopにもっていき、gifかpngかjpgで書き出して…という手順が必要になった。
ところがphotoshopにもっていく時点で色が褪色してしまう。
illustratorデータはもちろんRGBモード。
またもやphotoshopのカラー設定をいじってみたり、書き出しの際の設定を見直してみたり、illustrator側のカラー設定を見てみたりしたが、いまいち直らない。
何をどう検索したのか、Adobe CSはデフォルトではカラー同期されていないという文を発見。
Bridgeでカラー同期を行うといいらしい。

http://help.adobe.com/ja_JP/Photoshop/11.0/WSA0A53A1F-BF46-4624-82C6-340A70EFB8C4.html
以下転載
-------------------------------------------------
アドビアプリケーション間でのカラー設定の同期

Adobe Creative Suite を使用している場合、Adobe Bridge を使用してアプリケーション全体で自動的にカラー設定を同期させることができます。この同期によって、カラーマネジメントを行う Adobe のすべてのアプリケーション間で同じ色が再現されます。

カラー設定が同期されない場合は、各アプリケーションでカラー設定ダイアログボックスの上部に警告メッセージが表示されます。新規または既存のドキュメントで作業する前にカラー設定を同期させることをお勧めします。

1. Bridge を開きます。

Creative Suite アプリケーションから Bridge を開くには、ファイル／参照を選択します。Bridge を直接開くには、スタートメニューから Adobe Bridge を選択するか（Windows）、Adobe Bridge アイコンをダブルクリック（Macintosh）します。
2. 編集／Creative Suite のカラー設定を選択します。
3. 表示された一覧からカラー設定を選択し、「適用」をクリックします。

初期設定のいずれもが要件を満たさない場合は、「カラー設定ファイルの展開したリストを表示」を選択して、その他の設定を表示します。カスタムカラー設定ファイル（例えばサービスビューロから提供されたもの）をインストールするには、「保存されたカラー設定ファイルを表示」をクリックします。
-------------------------------------------------

私はCreative Suite のカラー設定を「WEB・インターネット用-日本」にしました。
やってみたら、ファイルを作り直したり、書き出し直さなくても、photoshopやfirefoxで正しい（と思われる）色で表示されました。
あら、いやだ。データの問題じゃなくて、adobeの問題なの？（それともmacbook？）
でもクライアントから色がおかしいと言われたこともあるので、今までの検証の努力もきっと正しい道なはず。
とりあえずこれでまた様子見です。