Windows XP SP3
Firefox 7.0.1
です。
直接の解決方法にならないかもしれませんが、参考までに。
cookieを制御するアドオンが入っている場合に、google.comやgoogle.co.jpの
cookieを受け入れる設定になっていても、Google表示設定で設定保存が
出来ないケースを経験しました。
当方上記環境でCookie Monsterを導入していますが、
当初検索結果が新規タブで開かず、Google表示設定で「検索結果を新しいウィンドウで開く。」に
チェックを入れても変化がなかった（設定変更が保存されない)ので、「おかしいな～」と
思っていましたが、「Accept Session Cookies from google.com」にチェックを入れると
設定変更が保存可能→検索結果が新規タブで開くようになりました。
なので、「cookie許可しているのに上手くいかないんだけど・・・」という方は、
session cookiesを受け入れる設定にすると、出来るようになるのでは？ と思いました。
参考になればと思います。
外していれば申し訳ありません。