Since you are now at 3.1.3, you can run Redsn0w 0.9.4 but browse to 3.1.2 ipsw to hactivate and jailbreak at 3.1.3. Unlock with Ultrasn0w again from Cydia.
That happens if you're trying to jb a certain fw and you're not actually on that firmware. Double check with f0recast from ih8sn0w.com that you're actually on 3.1.3.
Then try another computer is all I can say. Redsn0w does the best job for 3.1.3 on a 3G.
Try Sn0wbreeze 1.4, create a custom 3.1.3 fw in expert mode and select "activate" (where you'd normally select adding winterboard and Cydia). Then build the fw. Get iReb from ih8sn0w.com. Run iReb and shift+restore to the custom fw you built.
You might have some YouTube and push problems, but being on 3.1.3, you can install pushfix or pushdoctor to correct the problems.