コメントにより、参考になることが多かったのでまとめておきたいと思います。
今後同じトラブルを経験される人の役に立てば、私のトラブルも少しは意味のあるものに(笑)
＊その前に現状報告＊
現在のTime Machineの環境設定画面は以下の通り。
Time Machine のエラー
このバックアップは大きすぎるため、バックアップボリュームに保存できません。
との表示。つまりTime Machine用HDDの不足によるエラーという状況です。ただし、やはり最古のバックアップが -- と表示され、「Time Machine に入る」にしても、ロジックボード交換前のバックアップには戻れない状態です。そしてTime Machine用HDDには、「(ユーザー名) 2」という全く新規フォルダにバックアップされる状態のようです。現在HDDの空きが新規で必要な100GBもないので実行してはいません。
最終的な対応ですが、コメント検討した結果、単に新規バックアップ作成をしたいと思います。
本題のコメントまとめ
mackentoshさん、ystさんのコメントからも、ロジックボード交換のみの環境でTime Machineから前のバックアップ部分を簡単に引き継ぐのは難しいようです。
ただし、Takashiさん、Esさんのコメントから、ロジックボード交換によるMACアドレス変更に対して、ディスクイメージを変えるという方法があるようです。
参考: » TimeCapsuleじゃないNASを使って、TimeMachineを使ってみる | OpenMediaLaboratory
またRyoさんから、Time Machineが「バックアップボリュームが見つかりませんでした。」という場合での対処法として環境設定で再度ボリュームを指定するという方法で再認識される方法を教えていただきました。
他にも やまむら（ワンボタンの声）さん、Layzieさん、匿名さん からも参考となるコメントをいただき大変ありがとうございました。
追記 (2009/5/9)
前の記事、ロジックボード交換とTime Machine に Hattoriさんから、
http://rememberless.blogspot.com/2008/10/how-to-fix-time-machine-after-logic.htmlというコメントをいただきました。
↑ 半年以上たってますが...
最近Mac g4からMac Proに乗り換えて、TimeMachineのデータの引き継ぎ問題に突き当たりました。調べているときに、貴殿の投稿と上記参照の投稿を発見しました。
違う機種への乗り換えでしたが、うまくいきました。
とても参考になる記事の紹介ありがとうございました。