Your probably going to have to pull the SIM, put the device in DFU, and upgrade.
If you need to do it manually....
* iPhone 3.0.1 download (iPhone1,1_3.0.1_7A400_Restore.ipsw, 229 MB)
* iPhone 3G 3.0.1 download (iPhone1,2_3.0.1_7A400_Restore.ipsw, 230 MB)
* iPhone 3GS 3.0.1 download (iPhone2,1_3.0.1_7A400_Restore.ipsw, 298 MB)
Download the appropriate file to your desktop, once the phone is in DFU, click shift (option on a MAC) + Restore. Navigate to the file on your desktop and select it. iTunes will do the rest.
I have never had to do it, since I use AT&T, but I believe you need to leave the SIM out while you jailbreak and hacktivate the device. I think your issues are because the device is not activated (needs an AT&T sim to activate), and however your jailbroke it and unlocked it, it failed to "hacktivate".