iPhone Dev Team has released a new version of Ultrasn0w to fix issues with signal on iPhone 4, 3GS on the old baseband.
Note: Ultrasn0w 1.2.1 unlocks the older baseband on iOS 4.3.1 custom firmware. This will not work for newer baseband, and is essentially a fix for signal bar. It only fixes the compatibility and signal bar issues on the existing devices, which are jailbroken (with preserved basebands: 01.59.00 / 04.26.08 / 05.11.07 / 05.12.01 / 05.13.04 / 06.15.00) on iOS 4.3.1 using PwnageTool or Sn0wbreeze.
How to Unlock iOS 4.3.1 iPhone 4, iPhone 3GS
2. Run Cydia > manage > sources > Edit > Add > http://repo666.ultrasn0w.com and hit the Add Source button.
3. Now search for Ultrasn0w and install it. Restart when done.
If you are on a newer bootloader or baseband, there’s no software unlock available, so you can stop looking for one and may be you can try a Hardware based, Jailbreak-free Unlock for iPhone 4.