I can't remember where I found this out but, when you try to send the message and it says "Could not send", do this:
1. Go into SETTINGS> WIRELESS & NETWORKS> MOBILE NETWORKS and change the network mode to GSM
2. Wait for your signal to drop completely and then come back again
3. Then change it back to GSM / WCDMA preferred, and then try to send the message, it *should* send.
Bit of a palava but installing an app that takes you straight to the Net Mode settings dulls the pain a bit. I have Thomas Heinzelmann's Netswidget on my desktop.
Try that and see how you get on.