I have an iPhone 3GS running iOS 5 and baseband 5.16. After reading various blog posts and threads, I was told that in order to unlock it, I had to first upgrade it to the iPad baseband (6.15) and then downgrade it. Well, when I tried upgrading to 6.15, it took me halfway through the process and then said I had to first activate the iPhone. Not having a SIM card yet, I couldn't proceed. Now, WiFi doesn't work, Bluetooth doesn't work, calls, tons of things. The modem firmware is blank. The top left of the screen just says "Searching", and iTunes won't even recognize it. I think it may be bricked. Any suggestions?
Could it be that your iPhone 3GS was not compatible with the iPad baseband ?
See this post on the iPhone Dev Team blog.