I love the person who wrote this guide...
After 6 hours of fighting with my iPhone 3GS which was on the stock iOS 4.0 upgrade (but luckily had 3.1.3 SHSH blobs on Cydia), I was able to successfully use this guide to obtain a jailbroken, unlocked, iOS 4.0 device.
The only time I deviated from the guide was at the point where I restored to 4.0 custom firmware. When I tried it in DFU mode using the sn0wbreeze ipsw, it gave me a 1600 error. I then tried it in recovery mode using pwnagetool and it worked perfectly... For all I know, it may have worked in recovery mode using the sn0wbreeze ipsw.
I seriously thought I was screwed since the only blobs I had on file were 3.1.3, and I was upgraded to the latest baseband.
So, for the record -
Starting with: iPhone 3GS, totally stock (non-jailbroken, non-unlocked) iOS 4.0
Baseband 5.13.04
Old BootROM (sorry hopeful 3GS'ers with new one)
Ending with: iPhone 3GS (would be pretty amazing if I ended up with an iPhone 4), jailbroken, unlocked with ultrasn0w, iOS 4.0!!
Also should mention, I used like 3 different computers in the process of doing this... I used an older MacBook with an old version of iTunes for the Spirit JB because it was giving me issues on my desktop with 9.2, then I used (obviously) a PC for everything up to the final restore. Final restore I did on my Mac Pro.
This guide needs more publicity and the author needs... I dunno, sexual favors or something... I love you, random iPhone obsessive! You made my day!