I have an iPhone 3gs running 3.1.2 and modem 5.11. What I did was jailbreak with spirit and then unlock (for T-Mobile) with blackra1n rc2 through cydia.
Now I am unteather jailbroken and unlocked on a 3gs with the new boot rom.
I do have an ATT sim that I used to activate after the 3.1.2 restore (I have my 3.1.2 shsh on file w/saurik)
My steps were:
1. Restore in iTunes to 3.1.2 (changed the hosts file)
2. Activate in iTunes, but did not restore from backup yet