I had the same issue and if you read backwards your not alone. What I did that worked.
FAQ
This guide works for 1.1.2 OTB phones w/ the latest bootloader.
This method and guide was designed for nate true's jailbreak. But it will also work with either Dev Teams or MMI's Jailbreak. If you wish to use Devteams or MMi's, follow the same steps except skip 11. Perform step 12 first, and then proceed with either the Devteam jailbreak or MMi Jailbreak. Then, proceed to step 13.
Some have reported troubles with password saving, there's a fix: please add BigBoss's repository to your Installer
http://sleepers.net/iphonrepo There's two files to install, under 1.1.3 tweaks > Mailfix and Prefs fix.
I used the MMi Jailbreak which is labeled the official 1,1,3 updater or something official in the installer apps. All I can say is it worked. It took about 45 minutes to completly install so make sure you have a full charge on your battery. SKIP step 11 as it says above and don't forget to do step 13 or you wil have no phone. Hope this helps.
This can all be found in the unlock 1.1.3 with att and everything works thread