Were you in pwned DFU mode using Cydia (the answer should be yes)? Did you make sure your hosts file was clean and you were not running TinyUmbrella (also should be yes)? Were you restoring using a custom made firmware using redsn0w that is basebandless (hopefully)? Check these things.
Make sure your hosts are pointed to Apple by doing this:
Open tiny umbrella
Click on advanced
deselect the box that says "set hosts to cydia on exit"
Close tiny umbrella and proceed with the custom firmware restore