まずは、システム設定の問題なのか、ユーザ単位の設定の問題なのか切り分けるために、
ゲストセッションでログインするか、新規ユーザを作成してログインし、どのような挙動を示すか確認してみては如何でしょうか。

また現象も、もう一度整理して投稿して頂いた方が回答がつきやすくなるかと思います。
PageDownの挙動に問題があるのは、Upgradeした12.04だけという理解でよいですよね。

ありがちなのは、WindowManagerか何かにPageDownを取られていて、他のアプリケーションにキーが渡っていないという現象かと思います。
デスクトップ環境は何を使用されていますでしょうか。gnome classicでしょうか。Unityでしょうか。あるいは、それ以外でしょうか。
Unityはgnomeのコンポーネントを流用しているので、全く別のデスクトップ環境と比較できればなお良しですが、デスクトップ環境のショートカット設定でPageDownが何かに割り当てられていたりしないでしょうか。

この問題が起きるマシンで、ctrl+alt+F1などして仮想コンソールに切り替えた場合、PageDownは認識されますでしょうか。
(確認方法として適切なのはなんだろう。例えばemacsでF1(help) k PageDownなどとすれば、PageDown(ScrollUp)が認識されているか確認はできますが。。)
X上でだけ起きる問題なのか、コンソールでも起きているのか気になるところです。

LiveCDと問題の起きる環境で、
キーボード設定に差異は無いでしょうか。
xmodmap -pkeの実行結果に差異は無いでしょうか。

　最終報告です。完全に原因を極めたとは言い難いのですが、どうやら原因は 10.10から11.04までの間にインストールされていた何らかのパッケージを完全に削除しなかったことのようです。歯切れが悪いのは原因パッケージを特定できていないからです。
　先の報告で症状が出なくなった時にやったこととして、実は、deinstallパッケージの purge を行っていました(これは今回のトラブルに対処することを目的としたものではありませんでした)。職場のPageDownキーが認識されないマシンで、まず、10.10の時から積み重なった多くの不要パッケージの痕跡を消すために、apt-get purge を行い、設定ファイル等を含めて完全消去したところ、それまで自動起動するアプリケーションが3件あったのが、1件(電源関係)のみになりました(自分で設定した xmodmap関係の初期化ファイルを除いて)。この時点で PageDownキーがちゃんと認識されました。従って、upgradeで removeされた過去のパッケージのどれかが自動起動するアプリケーションに登録されていて、その設定ファイルか何かが影響を及ぼしていたようです(何故 PageDownキーだけがおかしくなったのかは謎のままですが)。
　というわけですので、削除されたパッケージは間違いなく purgeで設定ファイルを含めて完全消去するようにすべきであるというのが結論です。お騒がせいたしました。

　hmatuseさま、そうですよね。ちょっと不思議ですよね。ただ、パッケージAがパッケージBの起動を必要としており、Aの設定ファイルで Bの自動起動の設定を行うようになっていて、パッケージAを削除したために、Bの自動起動の設定のみが残っていたというようなことはないのでしょうか。本来 Aと Bの両方が起動されてキーが通常のように使えるのが、Aのみが削除されてしまったために、PageDownキーの動作が変になったと。Aの設定ファイルを消したことにより、Bが自動起動から外されて元に戻ったのではないでしょうか。
　バック用にポータブルハードディスクにインストールした 11.04の環境が残っているのですが、11.04では自動起動するプログラムが10以上あるようです。現在、--> 11.10 --> 12.04 とアップデートした後は 1つしかありません。この環境もそのうちアップデートするつもりですが、後からインストールしているパッケージはほとんど無いので、実際に使用している環境のように PageDownキーのみが認識されなくなるかはわかりません。また、何かわかれば引き続き書き込みさせていただきます。どうもありがとうございました。