We did have a bit of downtime with the service that processes our SMS notifications yesterday. However, it should have been resolved by the time you made this post, and I’ve confirmed that things are still working now. So I’m not convinced you ran into the same thing peter2 was talking about.
I suspect it could be the phone number format? I’d expect a format of 61 4 1234 5678 when dialing an Australian mobile (dropping the 0 since we’re texting from outside your country). Is it possible you had 61 04 1234 5678, or something else?
Also check for special characters. We should handle spaces, parenthesis, and hyphens OK in SMS numbers, but not the + symbol (or anything else I’m aware of)