Typically youd have the 06.15 baseband if you unlock with ultrasn0w but updated your iPhone baseband past 05.13.04. With this new capability, you can now downgrade specifically from 06.15 to 05.13.04 (even if you never had 05.13.04 on that device before). This gives you the best of both worlds: ultrasn0w unlock compatibility and a normal iPhone baseband with full GPS and the ability to use stock IPSWs again.
Create a new folder on your desktop called Pwnage.
In the folder place the current firmware of your device (which can be downloaded from here) and the latest version of RedSn0w (from here).
Extract the RedSn0w zip file by double clicking it.
Launch the redsn0w application from the redsn0w folder we extracted earlier.
Once RedSn0w opens click the Extras button.
Choose Select IPSW from the Extras menu.
Navigate to the Pwnage folder on your desktop, choose the firmware ipsw we downloaded earlier, and click Open.
Click OK to confirm your selection.
Tell RedSn0w whether you have a newer or older model iPhone 3GS.
Press Back to get back to the main menu then click the Jailbreak button.
RedSn0w will now prepare the jailbreak data.
Check the Downgrade from iPad baseband checkbox, uncheck Cydia if you already have it installed, and click Next to proceed through the normal DFU ramdisk steps.
Plug your iPhone into the computer and make sure its OFF then click the Next button
RedSn0w will now guide you through the steps to get into DFU mode. You can find more help with DFU mode here.
Hold down both the Home button and the Power button for 10 seconds.
Release the Power button and continue holding the Home button until RedSn0w detects the device.
Your iPhone will now be exploited with limera1n and reboot
Your iPhone will now be rebooted again and RedSn0w will begin uploading the new RAM Disk and Kernel.
RedSn0w will now inform you that its work is done. The rest of this process will take place on your device.
After showing some scrolling text, your iPhone will display the pwnapple icon and say Flashing Baseband. THIS STEP TAKES A VERY LONG TIME to complete and there wont be any feedback while its running. Please just let it be for the next 3-8 minutes! When the ramdisk has done its job it will reboot the phone on its own.
Once the phone has rebooted you will be on the 05.13.04 baseband. You can then follow this tutorial to unlock!
***A big thanks to the iPhone Dev-Team for making this possible!