Hey guys, I've been working on this for a day now. I finally got red sn0w to work with the os 4 restore .ispw. I kept getting the same errors that you had. This is what I did.

Download redsn0w 0.9.5 beta 5-3. It is VERY important to get the 3rd version. I couldn't do it with the beta 5-2.

RapidShare: 1-CLICK Web hosting - Easy Filehosting

Then I downloaded the 4.0/8A293 .ispw for my 3g. I put the .ispw file it its own folder on the desktop (It only worked after I tried this).

http://http://www.felixbruns.de/iPod/firmware/

I ran red sn0w just fine after that!

Good luck. If I can help any of you, let me know.