Because your phone has the iPad baseband on it. In order for you to use it, you must install ultrasn0w to unlock it and your phone will pick up signal with any sims including AT&T.
Thank you both. I reflashed the baseband and unlocked via ultrasn0w and that did the trick. Thanks again everyone!
For people who are in a similar situation I'll recap.
1) I was having problems with the iPhone 3GS old bottom on 5.0.1 after I unlocked with iPad baseband. The phone would randomly deactivate and asked to be restored in iTunes.
2) I restored to to 5.1 stock in iTunes thinking this would fix the problem. I did not realize at the time that once 6.15.00 is installed, there is no way to downgrade. Restoring to 5.1 does NOT resolve the issue.
3) At this time, I could not get past the activation screen even with an ATT sim as I had the 6.15.00 baseband.
4) I jailbroke 5.1 using Redsn0w. This got me past the activation screen.
5) My phone was stuck on searching/no signal
6) I reflashed the iPad baseband on 5.1 to no avail. Phone would not receive signal.
7) I finally was able to restore to 4.1 using saved blobs from Tiny Umbrella server running and pwned DFU mode in Redsn0w. (Luckily the person before jb and saved blobs as I bought the phone on 5.0.1)
8) At this point I inserted ATT sim and still no signal.
9) Reflashed iPad baseband in Redsn0w and unlocked via ultrasn0w in cydia as per recommendations.
10) Voila! iPhone gets signal again and GPS even works.
