What does it do when you try to send a text message? I noticed that when you create a new text message, the cursor is in the "recipients" field, not the "message" field. This drove me nuts and took me a minute to figure out. You need to add your recipient first, then move down to the message field and type your message and hit "options" then "send".
I have the same issue with my E61. About a week ago it just stopped sending text messages, however it is receiving SMS. Soft reset (return to the factory settings) would not help. Does anyone know, will hard reset be helpful?