This is a way you can downgrae firmware for 3.1.2.
http://www.redmondpie.com/download-the-new-iphone-os-firmware-3.1.2-aga809/
You will have to use your iTunes to restore your phone.
What you have to do is to trick itunes to think that you are applying 3.1.3
again.
Simply replace your ".ipsw" file with the file you are going to download and do restore.
Also even if you are not ATT customer apple should be able to assist you. For 90 days since you bought your phone their phone service is free after that you may need to pay for it, but it would be worth it for you at this point.
They can walk you through the process. They don't need to know if you are with ATT or if you aren't. They don't need to know if you phone is jailbroken or not.
Apple tech support # in US is 1-800-275-2273
http://www.apple.com/support/contact/phone_contacts.html
------------
Also there should some resources on the web were you can find about downgrading firmware from 3.1.3 to 3.1.2. At this point you don't have much to loose so I think it would be worth trying. I would probably go with Apply while their hold my hand just to make sure it is done correctly.
-------------
Additionally Apply has this Genius support where you can make an appointment and go to their store to receive some technical support from
their geeks who know their stuff.