OK, I did the restore but it's actually a different error;
"The iPhone ~iPhone~ could not be restored. An unknown error occurred (1604)."
I ran Recboot anyway, but it says "No device in recovery mode found".
What steps are you/have you taken? Did you create the firmware or are you using the one you found online? Also, how are you placing the phone into DFU?
I suggested iReb in an earlier post. If you haven't already, download it and use that. It will put the phone in the proper mode for a custom restore and if it gives you the 1015 after the restore, it can kick it out as well.