Okay, so restoring and setting up as a new phone works. I'm an AT&T customer by the way. I never received any texts that people tried to send me during the hours and hours my phone was out of commission, but I can send and receive now. I know it is a pain, but if you have all your contacts saved on your computer, you might as well give it a try.
how can an inbox be full? i've sent and received tens of thousands of texts over the years and never deleted any.
for what it's worth, i'm using at&t, iphone 4 with iOS 5 and am not having a problem as of now.