IPhone 4 issue: Message Box is Full

I had the iPhone since the original 2G version with the black and silver cover. I upgraded it to iPhone G, then to iPhone 4. Now I have downloaded iOS 5 and I keep receiving an error stating that my message box is full. I never had this problem before, nonetheless I listened and deleted some of my text messages from year 2008-2011. And then I leave my messages from the past few months. But then again I still got this message. I had my mailbox emptied and I am still receiving this message. Can someone please give me any suggestions on what should I do?
