The few times I had to deal with this on other's phones it was the text messages. Make sure you did a full shutdown and reboot (hold sleep/wake and slide to turn off). On one phone, nothing worked, even when I reset and restored from back up. That one I had to do full erase and set up as new (pain).
Here is some other ideas, link is named wrong