Can you restore a phone with an old version of iOS if that phone was never upgraded?
The official answer to this is no, you can not restore to a previous version of iOS other than the current one available from Apple. This is because iTunes is attempting to obtain tokens from the Apple signing servers to authorize the device when restoring.

The non official answer is yes, but requires some technical skills using iFaith. Post back if you require assistance down this path.