I'm in the same boat, afaik you can't unlock iPhone 3gs with newer Boot rom, ipt3 and baseband 5.12.01. and os 3.1.3.

If you just want to just jailbreak, the new spirit jailbreak provided untethered jailbreak.