You're on the incorrect baseband.... The only basebands supported by UltraSn0w are basebands 05.13.04 and below, or the 01.59.00 baseband on the iPhone 4, and the iPad Baseband flashed on 3GS's. Refer to this guide, as Justin has already laid out some of the basics and I've taken the liberty of adding some of the more specifics as well
No..... Go to the Settings app in your iPhone. Go to General > About. Then scroll down to "Model" and it should stay MBXXXXX or MCXXXXX. Reply with the exact model number including the MB or MC
The new bootrom normally does not allow iPad Baseband flashing, but depending on your serial number, if the 3rd 4th and 5th digits of your serial number is 135 or below, you can unlock using UltraSn0w. Otherwise, your only option is through an interposer or an IMEI/carrier unlock
Just wanted to make sure that UltraSn0w is out of the equation. My rec would be to get an IMEI/carrier unlock. It's permanent and if iOS 6 walks down the same path as iOS 4, there'll be a long way to go for the iPhone 3GS. If a new jailbreak comes out for any future iOS's, you'll have to make sure that your interposer is compatible with the device before you take the upgrade and potentially lock yourself out of using your own phone.