I am a UK O2 User who has a carrier unlock. Here is my story! (Not for the faint hearted, but if you have a 3.0.1 unlocked 3GS and want to jailbreak to 3.1.3 WITH an updated baseband, here's how to do it)

So here is the painful tale:

1. I bought my 3GS on launch day so untethered.
2. Backed up my IBSS/IBEC keys and tmp folders as told at the time.
3. Upgraded to stock 3.0.1
4. Not upgraded since
5. Used tinytss to generate my SHSH's
6. Upgraded to 3.1.3 stock (I have a carrier supported unlock).
6a. Created a new iTunes backup.
7. From DFU mode, downgraded to 3.0 - got error 1015 (which is the can't downgrade error). Used tinytss (saurik's would have worked I guess if I had done that).
8. Repeated step 7 exactly. Still got the error.
9. Ran redsn0w 0.8 and performed a jailbreak. The process crashed on "installing activation".
10. Held down home+sleep for 10s to put the phone in recovery mode.
11. Shift+Restored to my pwnagetool 3.1.3 custom.
12. Restored from my backup

I now have the latest baseband, my carrier unlock and a 3.1.3 jailbreak xD