My advice is to downgrade to 3.1 instead of 3.1.3.
all you have to do is the following
Download iOS 3.1 directly from [http://appldnld.apple.com.edgesuite.net/content.info.apple.com/iPhone/061-6605.20090909.PQ3ws/iPhone1,1_3.1_7C144_Restore.ipsw|Apple] or got to [http://www.iclarified.com/entry/index.php?enid=750|iClarified] and choose the right ipsw
Download PwnageTool 3.1 from [http://modmyi.com/forums/downloads/os-x/8/pwnagetool-3-1-32210/|modmyi], or [http://www.megaupload.com/?d=5ZUQ76I8|Megaupload]
You will need bootloader files 3.9 and 4.6 which you can download from here [http://www.iphone-hacks.com/iphone-downloads/file/131|bl39.bin] and [http://www.iphone-hacks.com/iphone-downloads/file/132|bl46.bin]
Now your are ready!
Put everything you downloaded in a new folder, open PT choose iPhone, click continue let it find the 3.1 .ipsw file that you downloaded earlier, click next and let it create the custom firmware. If you like you can choose expert mode and modify some of the features, like keeping original Apple logos instead of the pineapple one etc...
Now you have the Custom firmware, put your iPhone in DFU mode using PT, close PT and open iTunes (if iTunes opens while putting iPhone into DFU just close it after PT says Success you are in DFU and open it again)
iTunes will recognize that iPhone is in DFU and request that you restore. Using the Option (alt) key on your keyboard click on restore, a pop up will let you choose what firmware to restore from, navigate to your CUSTOM firmware that you created using PT. Now sit back and enjoy while it does the rest for you.
This by the way will Unlock your iPhone as well so you will be able to use it with any SIM card.
Enjoy :)