There are no actual settings on the iPhone to send SMS to non-iOS users. That is all handled by your carrier. The closest settings that you find for this is the MMS setting in Messages. The SMS setting there is only valid if you are attempting to send an iMessage and it will not send, it can be sent as an SMS if you turn on that switch. A true MMS also requires cellular data to be turned on. Otherwise, the carrier is in complete control of SMS/MMS. Sounds like they need to reset your account provisioning and start over, but they are the only ones that can fix it. They need to make sure that you have the correct carrier file on your device, since that controls the APNs necessary for connection to their network.