Grundsätzlich gibt es zurzeit kein Jailbreak für iPhone 3Gs (neuer Bootrom) auf iOS4.
Wenn du aber die 3.1.3 SHSH Blobs gesichert hast, kannst du auf die Firmware wiederherstellen und SPirit benutzen. Anschließend installierst du über Cydia von der repo ultrasn0w.com ultrasn0w Unlock. Der kann nämlich schon den Baseband auf iOS4 unlocken. Um herauszufinden ob du einen neuen Bootrom hast oder einen alten, benutz iDetector von iH8sn0w.com.

Wenn du alten Bootrom hast und auch 3.1.3 SHSH blobs hast, empfehle ich dir auf 3.1.3 downzugraden, mit Spirit jailbreaken, über Cydia Spirit2Pwn installieren und anschließend eine Custom IPSW für 4.0 über sn0wbreeze herzustellen und auf diese wiederherzustellen. Voila, Jailbreak auf iOS4

Falls du neuen Bootrom hast, einfach abwarten bis neuer Spirit released wird.