your message centre number may be incorrect, the correct ones are as below:
O2 Contract: +447802000332
O2 Pay As You Go: +447802092035
check your mobile phone manual to find the menu to check this, it's usally under message settings (on nokia's: Messages -> Message setting -> Text messages)
if you still have a problem, give o2 a ring, they will guide you though it.