If you reinstall using an OEM "system recovery" disk, it should also recreate the manufacturer's recovery partition scheme.
Lenovo should have a utility for creating such a recovery CD or DVD set on your laptop. If they don't you may need to request or possibly purchase these disk(s).
Create or obtain the recovery disk set, remove the original drive (put it aside safely in case you need to reinstall it), install the new HD, and then run the recovery program from your disk set.
If you need more info than that, it's probably best to just contact Lenovo Tech Support and request instructions on how to replace a HD and reinstall your OS and software.