My system gives me the same message. Since it appears you cannot get past that message, perhaps it is looking for the Windows 8 install files which include everything to reinstall your system, as was mentioned in the prior responses.
I did use the Backup and Restore utility to make a recovery CD, but it is funny, it would not boot on the system that made it, but it would boot on a newer motherboard.
There are many different versions of "Recovery" media. What you need it to do, is relevant to the discussion.
Edit: I just tried the process again and did not get the message. Using an 8 GB flash drive (doesn't have to be that large) I was able to complete. I do not know for sure why my earlier attempt failed, but perhaps your recovery system is not set up correctly. Can you hit Shift+Restart and get into the Recovery options and select those options without an error message?