細かい環境が解りませんが、CPUクーラーはコアにきちんと接触していますか？
最初の頃は多少熱が出ていても起動出来ていたのが、熱でコアが劣化してきて…というパターンも考えられます。
まずは上記を確認して最少構成（CPU、VGA、メモリ、FDD）で下記の様なチェックプログラムでFD起動してテストを行ない、OSの問題かハードの問題か切り分けを行いましょう。
http://www.memtest86.com/
>あるいはBIOSのアップデートが必要なのでしょうか？
ReleseNote等を見て必要そうな内容があるならば行いましょう。

やはりハ−ドの問題でしょう
コア電圧は１．４７５ｖ設定になってますか　あとは上記の方と同じくＣＰＵの熱暴走では。
　　　（コアとシンクのすり合わせがうまくいっていないのでは）
　

「Windows保護エラー」って一度出るとPCが覚えてしまう場合が有り、一度発生すると
環境を元に戻しても中々直らない気がします。
ちなみにSAFEモードでも立ち上がらないのでしょうか？。
SAFEモードで立ち上がるなら、Intelの最新チップセットドライバを入れてみるとか。

Celeron1.2Gはヒートスプレッダで覆われたFCPGA2なのでヒートシンクの接触不良と
いうのは発生し難いと思います。一度、WindowsとPeogram Filesのフォルダをリネーム
して環境を残しておき、再インストールしてみるのも手かと。

僕も熱暴走だと思いますね。ケースの外への排熱がうまく行ってないのでしょう。
いままでは電源やケースのＦＡＮの放熱力でケース内温度が安全内に保たれていた
のがＣＰＵを交換したためその処理が間に合わなくなっていると推測できます。

それにしても
＞これまでは、このメッセージが出てもリセットなり電源落としてまた入れたりする
＞なりすれば正常に起動できた
というのは中々不安定なシステムをお使いのようですね。
電源まわりにも問題あるのかもしれません。

みなさんいろいろアドバイスありがとうございます。セバスチャンさんにご紹介いただいたツールはまだ試していないのですが、いろいろ検証しまして、自分なりに切り分けができました。

私的結論として、原因は「マザーボード上のコンデンサ」にあるということになります。
ＣＰＵクーラーの装着は確実で、少しのたるみもありませんし、熱暴走に関しては前のＣＰＵでは真夏でもフリーズすることはありませんでした。

心当たりとして、ＣＰＵソケット付近を傷つけてしまった可能性があります。前のＣＰＵに使っていたクーラーがなかなか外れずに、勢い余ってマザー上のコンデンサに衝撃を与えてしまったのです。

で、例の症状があってから、その可能性をある程度予測した上で、マザー上のコンデンサを曲がっていたものに関して元に戻したら、いきなりちゃんと起動しました。

とはいえ、起動しないこともあり、根本的な解決になっていないのが現状です。
今度時間ができたら、ＣＰＵを前のに戻し、同じ症状が再現されるかを確認しようと思います。もし再現されたら、やはり原因はマザーですね・・・。マザーを修理に出すことも、検討したいと思います。

いろいろとありがとうございました。また、お世話になります。