Have you got the module set up correctly for the telstra network? You might have to change the message service center number that the module uses to send sms messages to the network. Mostly the module should read this from the sim, but occasionally this doesn’t work and you have to set the network parameters manually.
I haven’t got the at commands guide handy so I can’t tell you what the command is off the top of my head.
Will see if I can find it when I get into the office tomorrow.