If you are unlocked and rooted, I would boot into recovery and wipe the cache and dalvik cache. You might also need to wipe data, but I always save that as a last resort.
If you are just stock, no root, do a factory reset.
If those don't help, contact your service provider and tell them their...