I recently helped a co-worked jailbreak there 3G phone running clean 3.1 Firmware with baseband 05.11.07.
This tutorial will jailbreak the 3.1 Firmware for iPhone 3G[S]. IT WILL NOT UNLOCK!!!!!
DO NOT USE THESE INSTRUCTIONS IF YOU ARE TRYING TO UNLOCK.
THIS IS FOR JAILBREAK ONLY!!!!
1) Download PwnageTool from Dev-Team
2) Create a Custom IPSW for your device using PwnageTool
2a) BY DEFAULT IT WILL ACTIVATE PHONE. DESELECT THIS OPTION UNDER GENERAL!
4) If you are using a 3G[s] which has never been JailBroken/Pwned you need to use iReb
5) Use IReb to put iPhone into WhiteScreen Mode
6) Once in WhiteScreen Mode proceed to iTunes to restore using custom IPSW