What did you do to free application data space? Uninstall programs the regular way, I guess? I would guess there's a problem with tracker, which is too bad, since fixing tracker database problems is like equine medicine: shoot it. Which is to say doing a tracker database reset and killing all your contacts, messages, etc on the phone. Maybe someone else has a better idea, but I'm pessimistic.