Eu também possuo um iPhone 3GS, queria é mesmo fazer jailbreak. O procedimento acima não funciona para donos do iPhone 3GS, porque ao fazer downgrade para o firmware 3.1.2, o mesmo entra em contato com servidores da Apple, e então assim o downgrade é bloqueado.
Só é possíver fazer downgrade se você usar o método do Saurik, que exige um aparelho jailbroken para fazer backup de um arquivo do sistema.
Espero que o iPhone OS 4.0 seja desbloqueado!