I've had issues a bit like this with my Verizon iPhone 4 on redsn0w.
You need to use Select IPSW under Extras and pick the 5.0.1 firmware. Only then will any of the functions actually complete.
I'm not sure why it seems like you have to do this. Supposedly, support for 5.0.1 was added in a previous version of redsn0w. Of course, I was using the 5.0 firmware to jailbreak 5.0.1 before 5.0.1 support was official in redsn0w, creating the so-called 5.0/5.0.1 hybrid jailbreak, so that may have something to do with it.
If this is the case with you too, I recommend backing up and restoring since that seems to result in the most stable final untethered jailbreak.
Hope this Helps! ^_^
Edit: Like Lockon said!