That message will show up if you try to enter the recovery environment and the Recovery folder and its contents are not being identified (location or folder ID) or missing.
When the system comes back, you can try running a command in the Administrative command window and see if it completes.
Next you might try
then reagentc /enable
If all the components are configured correctly, the disable and enable commands should help.
But as Pat mentions, it might be necessary to do some type of repair/restore to get the Recovery configuration in the BCD store reconfigured.
The result of the first command should be something like the following, but the path might be different.
Windows Recovery Environment (Windows RE) and system reset configuration
Windows RE status: Enabled
Windows RE location: \\?\GLOBALROOT\device\harddisk0\partition1\Recovery\45a9a1d1-2552-11e2-8519-d25024cf0bd2
Boot Configuration Data (BCD) identifier: 45a9a1d1-2552-11e2-8519-d25024cf0bd2
Recovery image location:
Recovery image index: 0
Custom image location:
Custom image index: 0
REAGENTC.EXE: Operation Successful.