Lenovo Solution Center is complaining that Lenovo recovery media is not installed and everywhere I look, I can only find references to recovery media for Windows 8, not for earlier versions. Am I correct or am I missing something?
You *should* have created your own recovery media with Rescue and Recovery when you got the computer, if it isn't running it's too late -- you will have to buy one from Lenovo. Take a look HERE and the link to phone support to buy.
If it is still running, you simply make your own disk.