My mum had the same problem with her nokia 5800 and she is also on 02...I managed to fix it yesterday but I don't know how long for, this is what I did....
1> Connect your phone to computer and open Nokia PC Suite and click the backup icon, then perform a backup of your phone to the computer .
2>Disconnect your phone from computer and do a soft reset of your phone by dialing *#7370# (I think this sets your phone back to factory default settings and you may lose everything which is why I say to back it up first) The default lock code is 12345.
3>Connect your phone back to the computer using PC suite and click the back up icon again. This is when your going to restore things. Now I found that if I didn't restore the settings and restored everything else, the phone was able to send texts again. So I found that the reason why my mum couldn't send texts was because of the settings.
I don't know how long it will last for so im just waiting, I have noticed though that this happens with most nokia 5800 on o2!!
Hope this helps!
Let me know if it worked for you.
