iPhone cannot be restored. This device isnt eligble for the requested build

You cant restore or update any 3GS to anything but the latest version 3.1.3
unless you have your shsh's saved thru cydia.
Try this for Windows http://www.iclarified.com/entry/index.php?enid=7557
Macs: http://www.iclarified.com/entry/index.php?enid=7556

If it still gives you the same message you dont have them saved thru Sauriks Server but worth a try.

-- edit --
i just repeated what Applejuiced just said..

after it's reloaded, you may have to remove the line to activate the phone.

double post. (I'm not making a good first impression here.... )

Upgrade to a pwned 3.1.2 ipsw.

iMrNiceGuy0023 said:

how do I save shsh's thru Cydia?? are they automatically saved?

Click to expand...

Open up cydia and look at the top of the screen it should list if u have shsh's saved and for what firmware.
Assuming u were jb before and clicked the "make my life easier" option on cydia.

iMrNiceGuy0023 said:

im currently jailbroken on 3.0 right now, and it says my device has SHSHs on file for 3.1, 3.1.2, 3.1.3

Click to expand...

If you are currently jailbroken and have old bootrom (yes to both I think), make or get a custom restore 3.1.2 IPSW, put your phone in recovery mode and use iTunes to select the custom restore 3.1.2 IPSW. Will bypass checks. You have to option+ (mac) or shift + (PC) the restore key to be able to browse to 3.1.2 custom restore IPSW.. It should start with 2,1......

Don't select 3.1.3 by mistake.

iMrNiceGuy0023 said:

how do I save shsh's thru Cydia?? are they automatically saved?

Click to expand...

Once you or even former owner if there was one, pushes Make my life Easier button, all SHSH for every new version of firmware is stored automatically. So yours was started when 3.1 firmware was signed and will keep collecting as new firmware is released (as long as you remain jailbroken)

You are good to go then iMrNiceGuy0023.
Listen to what dhlizard said above.