I experienced a similar problem yesterday after migrating to a new phone.
Let me guess… are you a Verizon Wireless customer?
I had to call them a couple times to get my phone to activate; eventually I had to read the IEMI and ICCID numbers to them and after a LONG time, it seemed to activate. Everything seems fine except for texting non-Apple devices.