As mentioned in previous posts, it is warned that you SHOULD NOT upgrade to iPhone 3.1.3 if you’re using a software-unlocked (e.g. via ultrasn0w) iPhone 3G/3GS. Otherwise, you will end up with a locked iPhone again. While you upgrade to iPhone OS 3.1.3, the baseband of your iPhone is also upgraded to v5.12.01. That’s why your iPhone is locked again after the OS upgrade.

Presently there is no unlock solution for iPhone 3GS user. But if you’re using iPhone 3G with older version of bootloader 05.08, you may use Fuzzyband to downgrade the baseband version from 05.12.01 to 04.26.08, which can be unlocked using ultransn0w.

Note: Fuzzyband only works on iPhone 3G.

How To Downgrade Baseband From 05.12.01 To 04.26.08

1) You need to jailbreak your iPhone. As you have already upgraded to iPhone 3.1.3, please use redsn0w to jailbreak the iPhone.

2) Launch Cydia and search for “Fuzzyband”. Then download and install this application.

3) Go back to home screen after installation. Tap “Fuzzyband” icon to launch it.

4) Tap the “Downgrade” button to kick off the baseband downgrade.

5) Once you complete the baseband downgrade to 04.26.08 successfully, you can download ultrasn0w to unlock your iPhone. For instructions, you can follow the my guide here.