Time Machine does not recognize my MacBook Pro

Solution 1:

Each backup disk is associated with your MacBook through both your computer name and the MAC Address of the first network port. When you get a new logic board then that MAC Address will have changed, even if you use the very same internal hard disk (and hence the same computer name).

If you would still have used the same internal hard disk, then you could have followed the instructions on 10.5: Repair Time Machine after logic board changes and 10.5: A script to fix Time Machine after hardware repairs from macosxhints.com (be sure to browse through the comments on that site as well).

However, as you restored some settings, it seems you also have a new internal disk. In that case, I think it is not a good idea to try to associate your old backup with the new hardware. See How do you re-associate an Airport Time Machine backup after migrating to a new mac?

Note that holding down Option while clicking the Time Machine icon will make "Enter Time Machine" change into "Browse Other Time Machine Disks", wich allows you to restore from any backup.