I believe how Redsn0w works is that you restore your phone like a regular one, and then you run redsn0w afterward... so I would think your problem is with the restore and not redsn0w.
Have you tried to run the restore again? Or is that the problem you're having.. if you hold down the Home button when you plug in your phone to iTunes that should tell iTunes that it needs to be restored.
Or you could try putting it into DFU mode..
http://www.iclarified.com/entry/index.php?enid=1034
Or if you're getting to the part where you've run redsn0w and the phone has to restart.. I would echo what secretanchitman said.. make sure you are pointing redsn0w at 3.1.2 and not 3.1.3.