I had kind of the same problem a couple months ago, was stuck in recovery & it would get stuck trying to restore. I had to put my phone in DFU mode and then restore it, nothing else would work. You may be able to do it this way & still use 3.1.3 but I'm not sure.
I'm really sorry this is like way late, I had tried to find this post several times to see if you had replied but couldn't. Anyway, if you haven't fixed it yet I plugged my phone in let iTunes recongnize it, leaving it plugged in, power it off then put it in DFU mode. iTunes should come up saying the device is in recovery mode & needs to be restored. Maybe try to restore it with 3.1.3, if you have the firmware d/l by holding shift then clicking restore, if that won't work then you make have to do a complete restore which will probly update to whatever the new firmware is. Hope this helps & sorry once again.
And if you end up updating to iOS 4 I'm not sure why you don't want to, if it's because you think it will be slow you can download zToggle to disable multitasking and Wallpaper, and use your preferred applications.
you can use redsnow for your version of IPSW to kick it out of recovery. Try TinyUmbrealla. I have never use it before but it has an option to kick it out of recovery.
I will tell you that you will erase all your data and info.
If redsnow does not work try this
1. Place phone in DFU mode. (Hold power and home button down)
2. Connect to iTunes
3. Itunes will tell you, you need to restore.
4. Make sure you have the IPSW you need (i.e. 4.0 or 4.0.1)
5. Click "Shift" for windows or "Option" for Macs with a Click
6. With the option to choose, choose the firmware you want to update to
7. Click and itunes will the rest.