After I replace a dying HDD, is it better when booting up to the Recovery USB stick to choose Restore from Time Capsule or should I Reinstall Lion first, putting the OS bits together on a blank disk, and then restore my data? Does it matter?
The problem is that your backup might be corrupted, depending on what happened with your hard drive. A restore would probably work but it would be a drag if you got far into it only to have it hang because of a corrupted file.
I'd reinstall Lion and then use Setup Ass't; it comes up once you get booted the first time, and then let it migrate your stuff from the TM backup.