That's strange. The IPSW for all 4s phones should be the same. If it was locked, it never should have connected in the first place. Although, "locking" is a bit different with CDMA carriers than it is with the GSM carriers.
Do you know anyone with the 4s currently on Verizon's network? In addition to trying to download the IPSW manually like Keith suggested, you might pull up the carrier data for your friend's 4s on Verizon. If it's reading the same, it shouldn't be an issue. If it's different, there's probably a bug in the update system if you're finding this issue widespread.
Unfortunately, I dont have any friends available at this time to do that .
Another thing I noticed in redsn0w is that it is not displaying a phone number in the list of information. I read earlier about how turning on/off an unactivated phone could possibly wipe out the SIM data or something. Im taking the phone to Verizon today, and im hoping they can fix it so I can spare the 40 minute drive to my nearest apple store.
For the record, I just popped my SIM slot open, and there WAS a Verizon SIM card.