Peter,
In the past, I have had some devices show that error but I was able to simply hard reset the device and it booted fine.
Was the phone jailbroken before? Also, I would make sure you are attempting the restore in DFU mode versus Recovery mode. It sounds like it is having a conflict with the baseband which is why the device is not allowing itself to boot. You might also try using TinyUmbrella to fix recovery.
If you continue having issues, let me know. Also let me know if you are using PC or Mac and which OS you are running.
Let me know how it goes! If it doesn't work I may have a few other tricks up my sleeve.
Jonathan