I had the same problem, in my case the issue was that the file
winre.wim was missing from my system. It contains the Windows recovery files.
Inserting a Windows 8.1 DVD didn't help.
To get a copy of a Windows 8.1 winre.wim, I had two options (there may be others).
One - On a different Windows 8.1 system open an elevated command prompt and type:
This copies the winre.wim file from the hidden recovery partition to C:\windows\system32\recovery, copy it from there. When done enable the Windows Recovery environment again:
Two - If you have a Windows 8.1 ISO or DVD, mount the install.vim and copy the winre.wim from there. Create an empty directory such as C:\mount. Then again open an elevated command prompt and type:
dism /Mount-wim /wimfile:D:\sources\install.wim /index:1 /mountdir:C:\mount /readonly
then open C:\mount\windows\system32\recovery and copy Winre.wim from there. Unmount:
dism /Unmount-Wim /Mountdir:C:\mount /discard
Now that you have a copy of Winre.wim, copy it into C:\windows\system32\recovery on the PC that is missing it.
Finally again in an elevated command prompt:
This will move Winre.wim and enable the recovery environment, you should now be able to create a recovery USB drive.