Hi Philip,
Find out form veritas if they have any tool which could use Microsoft ASR which would be a lot easier than all the above process, if not, you can follow Williams.
Few more points to add:
1. Make sure to have Windows Service pack at the same level when it was at the time of backup. If it was at SP2, the new installation also should be at SP2. This is because there are few files like hal.dll which will not get restored with system state restore.
2. Restore the C and System State together and reboot
3. I would always prefer the new HDD being a little bit larger than the older HDD because the Disk geometry might vary between vendor to vendor