Hmm this is a strange problem, I've seen replacing the SIM card work for others. The apple rep could be right, your sms center number could be wrong (replacing the SIM card should have corrected the number).
You could call back AT&T and have them check your sms center number and correct it if necessary. Or you could get the sms center number from them and enter the following on your iphone (as if you were about to dial a regular phone number):
*5005*7672*+NNNNNNNNNNN# then hit SEND
( NNNNNNNNNNN = the message center number. Dont forget the + sign before the number )
Alternatively, if you have another AT&T phone laying around, you can try removing the SIM card from your iPhone and inserting it in that other phone and see if you can send and receive text messages. That should help figure out if its a problem with your phone or with the network.