Попробуйте все таки еще раз очистить кэш Сообщений: Настройки\Приложения\ - найдите Сообщения, зайдите в них и выберите пункт Удалить данные\Очистить кэш.
Если не поможет, то пробуйте тогда сделать сброс настроек.
