Here is the NEW Unlock as of June 04, 2012....
The iPhone Dev-Team has released UltraSn0w 1.2.7 to bring unlock support for some older basebands on iOS 5.1.1.
iPhone Dev Team's iPhone 4, 3G, and 3GS software unlock, now with added PwnApple. Compatible with iPhone 4 baseband 01.59.00 and iPhone 3G/3GS basebands 04.26.08, 05.11.07, 05.12.01, 05.13.04, and 06.15.00! Thanks to @sherif_hashim and @Oranav for contributing baseband crashes.
You can install UltraSn0w 1.2.7 from Cydia following a jailbreak.
iClarified - Apple News - iPhone Dev-Team Updates UltraSn0w to Support Unlocked Basebands on iOS 5.1.1