標題のとおりですが、Firefox4にしてからリンクを新しいタブで開き、そのタブ内でリンクをクリックした場合に戻るボタンが有効にならず、前の画面に戻ることができません。
2回目以降のリンクではちゃんと戻るボタンが有効になります。

新しいプロファイルを作成して試してみましたが挙動は同じでした。
他の人はそういう症状ないんでしょうか？

※質問するときは、フォーラムの利用に関するご案内 、とりわけ 質問するときは に目を通し、Firefox のバージョンだけでなく OS の種類やバージョンといった使用環境についての最低限の情報を書き添えましょう。

だれでも簡単に試せる汎用的な検証手順として、下記のような操作をおこなってみました。

（1）Firefox 4.0 で「Yahoo! JAPAN 天気情報」
http://weather.yahoo.co.jp/weather/
のページを開きます。

（2）その中の「各地の天気」にある「北海道」のリンクを新しいタブに開きます（中クリックまたは [Ctrl] + 左クリック）。
http://weather.yahoo.co.jp/weather/jp/hokkaido.html

（3）このページを開いたタブ内で、「各地の天気」->「北海道」のうちの「道北」を左クリックして同じタブ内で遷移します。
http://weather.yahoo.co.jp/weather/jp/1a/

（4）「各地の天気」->「道北」のうちの「宗谷地方（稚内）」を左クリックして同じタブ内で遷移します。
http://weather.yahoo.co.jp/weather/jp/1a/1100.html

この一連の手順の中で、（3）で開いた「道北」のページから「北海道」のページに戻ろうとしても、[ナビゲーションツールバー] にある [戻る] ボタンが（グレーアウトして）有効化しないが、（4）で開いた「宗谷地方（稚内）」のページから「道北」のページに戻る場合は [ナビゲーションツールバー] にある [戻る] ボタンが有効になる――という話ですか？
（4）->（3）へは戻れるが、（3）->（2）へは戻れないと......。

当方の環境（Firefox 4.0 on Windows XP SP3）ではご提示のような現象は再現できません。（3）でも（4）でも [戻る] ボタンは有効に機能しています。

[戻る] の情報は [履歴] に依存しているわけですが、仮にオプション設定で履歴の保存を無効にしていても、Firefox を起動中はメモリ上に記憶されているため普通は [戻る] ボタンは正常に働くはずです。
しかし、起動中であっても [最近の履歴を消去] で表示したページの履歴を消してしまえば、メモリ内のデータを含めて消されるので、その時点で [戻る] ボタンはたどるべき履歴を失いグレーアウトします。

本件の場合、ユーザーがそのような操作をおこなっていないなら、Firefox の通常動作を阻害している何らかの要因があると推測できるのですが、であれば、
アドオン類が影響している可能性は低いように思われます。

ただ１点、セキュリティ対策ソフトなどで危険な Web サイトを監視するような機能（例えばサイトアドバイザーといった名称の）が、Firefox の動作を阻害している可能性は考えられます。
アドオンと異なり、外部プログラムとして Firefox の動作に食い込んでくるものなら、Firefox を新規プロファイルやクリーンインストールで試しても、ということはありえるかもしれません。
このあたりは点検されましたか？

とりあえず以上です。外してたらすみません。

丁寧に回答していただきありがとうございます。

セキュリティソフトにMcAfeeを使用していまして、機能の一部にSiteAdvisorというものがあるのですが、これを無効化することで正常動作するようになりました。

以下と同じですね。
http://forums.mozillazine.jp/viewtopic.php?t=11259