This is Vista Backup and Restore's behavior on the less-than-ultimate versions. This weekend I reinstalled Vista Home Premium (again) and did a backup ahead of time. After reinstalling Vista clean, I tried to restore my files and it said it was not the same computer! There is an option, however, to restore files from another computer (I think you have to do an "advanced" restore) and it works.
Now the bad news: when you use the low-end version of Vista Backup and Restore and tell it you want a full backup, you DON'T get a full backup. It decides which "documents" it thinks are yours, and backs up those. There are a load of files, including .exe, that it doesn't backup.
Luckily for me, I had done a complete robocopy of my C: drive a week ago, so I wasn't completely screwed. I did get burned, though, on software downloads like ZoneAlarm that install with an .exe kicker.
Moral: If you want a full backup, Vista (Home Premium) Backup and Restore full backup doesn't do the job.