I have this same problem. Read this thread.
And have done a lot of stuff trying to solve this problem.
I just noticed I have 90.3MB tied up in ******* Dialer Storage (idk how its so high) But whats stored in this and will I be fine clearing the cache?
I also just cleared 25.5MB of facebook cache.
This phone sure does love to hold onto information.