I have had same problem 2 days before...When i was jailbreaking 3gs 3.1 with old bootrom.....I pressed "yes" instead of "no" when redsn0w confirming about old or new bootrom and phonne stuck in recovery mode....So what i did that i jailbreaked it again.....In your case this must b like this....
1: Open red sn0w and select 3.1.2
2: Press next and if redsn0w confirming about bootrom then please press "Yes"(As its MC)...
3: Put a check on "Cydia" and press next and now follow instructions given by the redsn0w...
4: Redsn0w now jailbreaking your phone wait for the process to finish!And now your phone will be ok!
Note: If phone stays in "Recovery Mode" even after this procedure then chose "No" instead of "yes" in step 2....Hopefully this will solve the problem!
Good luck!
المفضلات