I have had this problem a few times, and previously it's been fixed by checking/resetting the SMSC number (by dialing *#*#4636#*#*). It started happening again yesterday, but this time my tried and trusted fix isn't working.
Thanks, got the new SIM. Setup was not quite straightforward - the first instruction is 'Using the old SIM, text the word READY to ...', but the reason for needing the new SIM was because my phone would not send texts! But I phoned 789 and they manually activated the new SIM for me, so all is well.