I think I have solved on my HTC incredible, which has 8GB, says 7GB remaining, but I get Phone Storage Full errors, and I cannot download apps nor MMS and other problems
I had my Exchange email set to download all my email and calendar items, and I think the storage was actually full and misreporting space. I set the email sync to get only 30 days, waited for a long re-sync (which effectively un-sync'ed many emails), and now all failing apps are working again and phone storage full errors gone.
Therefore
a) check apps and storage memory
b) check email (Exchange, Gmail, Facebook, or other sync settings)
c) look into optomizing those settings
d) see if resolved
e) report here on this and other similar posts