HT4623: Update your iPhone, iPad, or iPod touchLearn about Update your iPhone, iPad, or iPod touch
Currently Being ModeratedJan 18, 2013 6:57 PM (in response to brushard1)
I'm assuming you just updated your 3Gs to 6.0.1 and you are now getting this message. This normally means that your iPhone was unofficially unlocked through it being hacked/jailbroken and it has now relocked to the original carrier.
Call AppleCare and give them the model and serial number and find out which cell carrier it is locked with then contact that carrier and see what the process is to officially unlock your iPhone.