About the only thing that works is to use that failure as your break of the contract with ATT. Then you get them to transfer the phone number to another company. It's not a phone setting since the SMS makes it to other ATT customers.
So it's clearly their backend at fault. If there is a phone setting to allow this, again ATT supplies that.
They did change the plan months ago. http://www.technologytell.com/apple/76635/new-att-customers-soon-to-be-limited-in-sms-plan-choices/ and to enforce it, you bet it knows your phone's id.