This is, unfortunately, expected behavior. Whenever you activate an iPhone (which you do as part of an OS install) it talks to Apple's servers and does various things like exchange crypto certs for APNS, etc. It also checks the IMEI of the phone to see what carrier Apple sold it to, and validates the SIM is valid for that carrier (if you buy an unlocked iPhone in a country where you can buy either locked or unlocked phones the vendor will actually copy down the IMEI number of a normal locked phone, and then enter in their system where it gets pushed to Apple's servers as an unlocked phone, there is no physical or configuration difference on the phones).
The easiest way to get it activated is (as you surmised) to use an AT&T SIM. You mentioned you have an iPhone 4, you can activate it with that SIM. There are plenty of companies that sell microSIM to SIM adapters, but if you want to do it right now you can just place the micro SIM directly in the iPhones 3GS's SIM try with tape. I would not recommend doing this on a device you intend to keep the SIM in for a an extended period because the SIM is likely to come loose (and jam the SIM tray), but if you are just inserting it, activating it, and removing it you should be fine so long as you are pretty careful with how you apply the tape and not shaking the phone too much.
You can't update your phone to iOS 5.0 Not even if you have your SHSH saved. So nothing you do will allow you to install 5.0 right now. At least for the time being.
Your only option is 5.01. The problem is that apple is no longer signing 5.0 and no shsh blobs will help you neither because a new security measure implemented on all 5.X
So if you need an unlock in order to use your phone I would highly recommend not updating to 5.01 because UltraSnow is currently not working on 5.01 despite of what baseband you have. No even with 1.59 baseband (but this is just until ultrasnow is updated to work on 5.01)
If you don't need an unlock then you can safely update to 5.01 and do a tethered jailbreak using the latest redsn0w and pointing the ispw to 5.0
And before doing anything please update to the latest iTunes.
I hope this helps.
Best Answer
You are using a version of redsn0w that cannot handle that specific version of iOS. You will need to find the correct version.
Here is a guide that might help: http://technorati.com/technology/gadgets/article/how-to-jailbreak-ios-435-on/
And it is of note that they have not released an untethered jailbreak for either 4.3.4 or 4.3.5, which means you will have to load the IPSW in redsn0w and apple the crack (select the option "just boot tethered") every time you cycle the power.
Also of note that the redsn0w .8b series is reserved for the iOS 5 betas.
You can see the full list of versions here: https://sites.google.com/a/iphone-dev.com/files/home/
Off hand I don't remember which will jailbreak 4.3.5 but give the latest .6 series a try first and work backwards.
And a word of caution, be wary of Redmond Pie, fromy experience they are far from a credible source for help and frequently report inaccurate information or often times completely spread misinformation. They seem more concerned with "getting there first" than actually reporting steps that you can rely on.