So, I booted from the setup DVD, selected <em>Restore from TimeMachine</em>, plugged in the external backup drive, selected it and setup started scanning my backup. 

So far, so good, but when setup asked me for the target of the restore, the selection list was empty. Hmm, maybe it is not really restoring everything and needs a running OS on the target? I installed a fresh OS to find it out. 

After having installed the OS, it gave me the internal drive as a target choice. Strange, it is then partitioning the drive when restoring. 

Later I found out that simply rebooting at the time I installed the OS helped some people. What hepled me was the third beer when the restore crashed after some 2 or 3% done. 

I don't know why but I just tried again. This time it worked. Width exceptions: 

iTunes

iTunes is telling me this is not an authorized computer any more. I have some computers left to authorize, so I just added the (not so new) machine. 

Sadly, I cannot deauthorize the crashed mainboard. I will reset my account on another day. 

Mail

Mail was behaving a little strange after the restore. The mailboxes were there, but no mails were showing in the application. Rebuilding the mailboxes (in Mailbox/Rebuild) helped. 

My Notes were somehow gone, I has to restore them from the Time Machine. 

Attach Backup

At least I thought that would be easy. Launching the Time Machine, select my notes and hit restore. You can imagine how shocked I was to find my Time Machine completely empty. 

After some more investigation I found that the reason is my changed MAC address. 

Repair Time Machine after logic board changes shows the two places where you have to poke the new MAC address into the backup db. 

Bottom line: Time Machine was a good thing to restore from because my backup was extremely up to date, a single email got lost. However, plan a day until your machine is running again.