You would need to download the lastest redsnow, and jailbreak your phone (which is tethered for your software) as well as update to the 6.15.00 ipad baseband. After that is done, just install ultrasn0w and your finished. remmeber that any time you turn off your phone you need to connect it to the computer in order to turn it back on since its tethered
You would have to be on 4.3.3 to upgrade the baseband. You shouldn't run redsn0w anyway on 4.3.5 unless you want a buggy tethered jailbreak.
But the reason why RS isn't even working for you is bc you're using the wrong version.
You can however downgrade to 4.1 bc you Apple still signs that for the 3GS then you can use RS for 4.1 to jb and upgrade the bb to unlock (just remember the iPad BB upgrade can break the GPS function).