Well this may come late in the treat, but just to add my moneys worth...
I arrived in the UK last night, send two messages from my phone and that was it, afterwards any message I tried to send came up as WARNING message not sent, thinking I was out of funds on the phone, thought no further about, untill I brought a local operator sim card, set up the new sim, received all the required details for sms, MMS, internet etc... still sms issues, after hours of looking for ways to fix the problem came upon this tread.
solution was a simple down load of the app GO SMS.
I found this rather interesting, I've had my Samsung SL (S GT-I9003) for just under a year wail living in Indonesia, I had no problems with sms or anything else with either the phone or provider.
I can only conclude that Samsung are not selling a faulty product as some would say on here, but most likely there is an issue between Samsung and some Western mobile providers(though had no problems with sms function in the USA wail on holiday over there) what that issue may be I could not say, maybe a coding issue or maybe Apples issues with Samsung namely the S and Tabs products are having something to do with this issue. My crystal is not able to tell me at this point