New laptops usually ask you to make a set of recovery disks and will persist in showing this message until it's done. Once done it can not be used a second time.
You can still use the recovery partion to restore from. If the files have been deleted from the recovery partition and you don't have the disks, you're screwed.
You would then have to contact Toshiba and purchase a set of recovery disks from them.