I'm clueless why it would do that. You have proper version of baseband, so ultrasn0w should do the trick. I hope someone comes here and helps you soon.
If you start reinstalling iOS make sure you do it using sn0wbreeze in baseband preservation mode. If you have SHSH for your firmware you could try reinstalling, if not, 4.3.5 is what you can go to now. BASEBAND preservation, write it somewhere visible.
Right now, let's wait, maybe someone could help you. What you could do is stick that SIM into some other phone and see if it works. You could stick a micro SIM into a regular SIM sized phone; contact area is the same - get it out with a needle.