None of below is my original idea, but I put the steps together although other people might have posted already.
Problem
On a previously jailbroken iPhone, after upgrading to firmware 3.1.3 using standard method via itune, iPhone cannot be jailbroken using existing ways to jailbreak.
What can be done here
Go back to firmware 3.1.2 or whatever you were using prior to upgrading to 3.1.3, jailbreak, and restore from back up
What cannot be done here
Go back to previous baseband nor unlock iPhone
Must have for the procedure
If you were using Cydia then you are fine. SHSH hash for your iPhone for whatever firmware you were using previouly - this can be obtained from cydia server if you were using cydia GUI with previous firmware
WHAT TO DO
1. First obtain ECID for your iPhone - I have both PC and Mac, but I used Mac to find my ECID. Just put the iPhone in the recovery mode and look under about this Mac to see Apple iPhone info. To put it in the recovery mode, turn off the phone and connect to USB while holding HOME button.
2. Download fw-umbrella-semaphore from http://thefirmwareumbrella.blogspot.com/ and run umbrella to get shsh hash. Make sure to select Cydia server and your previous firmware.
3. Run tinytss from commandline, but make sure to add gs.apple.com to your host file with 127.0.0.1 before running it. Under Mac, you have to edit /etc/hosts file and add 127.0.0.1 gs.apple.com. Under PC, you have to edit C:\Windows\system32\driver\etc\hosts (I could be wrong but something like that) file and add gs.apple.com 127.0.0.1.
To run tinytss, open a commandline window and cd to its directory. Make sure shsh file is in the same directory. Under Mac, type java tinytss.jar -f whateveryourshshfilenameis.
4. Now your can do a restore on iTune to go back to previous firmware. Make sure you have previous firmware first, and click on "restore" on iTune while holding alt-option key on Mac or Shift key on PC. When browse window pops up, browse to where you have the firmware file and start restoring.
** you will get an error when restore is almost done. This is NORMAL!!! Just repeat the restore again... However, you will get the same error message! This is NORMAL again!!!
5. iRecovery has to be run now. Download iRecovery from http://www.ihackintosh.com/2009/07/irecovery-iphone-recovery-mode-loop-restart/ and run it.
Command is
iRecovery -s (this starts a new prompt)
(then type the following)
setenv auto-boot true
saveenv
/exit
6. Almost done!!! Just reboot iPhone by holding power and home buttons at the same time. When phone reboots, you are back to the previous firmware version.
7. Run blackra1n to jailbreak and then do restore from your backup.
