Before using the Recovery Image it is necessary to set the server hardware clock to a relatively accurate current time. Enter BIOS mode. Set the current date. Save and exit.
If the clock is too far off the recovery will fail.