Not sure if this post will help anyone, but just thought I would post my experience in updating and unlocking my iphone.
First thing to note: iphone 3GS, iOS 4.1, 6.15.00 baseband. The phone was already unlocked when I got it, so I had never been through the process myself.
I updated to iOS 5.0.1
I used redsn0w V0.9.10b5c, f0recast V1.3, and itunes V10.5.
I highly recommend checking out iclarified website, there are excellent guides to do all kinds of things there.
I had difficulty, but only because I misunderstood the procedure. I thought the custom IPSW included the jailbreak. It does not. I had to restore to the custom IPSW, then restore my backup, then jailbreak, then unlock. When I finally did things correctly, it went very smoothly (imagine that).
So for what it is worth, here are the steps I went through.
1. updated itunes to newest version
2. used redsn0w to make sure my SHSH blobs were backed up
3. used f0recast to check if I had new or old bootrom
4. redsn0w to create custom IPSW
5. itunes to (shift/click) restore the custom ISPW
6. redsn0w to jailbreak
7. itunes to restore the backup of the phone
(I think it was this step in which my phone hung on the reboot. itunes restored the backup, but the phone would not finish rebooting. I used redn0w option to ‘just boot’.
8. ultrasnow to unlock
If anyone has comments on how this procedure could have been done better, please feel free to add them.