Do calls and data work?
Can you receive incoming texts?
Do all texts to all numbers fail?
Are you sure that you're not trying to send MMS messages which need cash credit to cover the cost (30c each)?
Some SMS messages will be converted to MMS messages automatically by many phones - e.g. long text messages, messages with pictures including some emojis, texts with accented characters etc.
Hope this helps.