Поставил вчера впервые Ubuntu 16.04 LTS на виртуальную машину и сразу же столкнулся с похожей проблемой: не запускается Менеджер приложений. Из изменений, которые я внёс после установки - привинтил skype. В системе я новичок, ориентируюсь плохо. Облазил разные форумы, перепробовал всякие советы. Ничего не помогло. Решил просить помощи тут и сначала подумал перепроверить версию установленной системы, чтобы ненароком не угодить не в ту тему форума. В итоге неожиданно наткнулся на решение проблемы. Оказалось, что ларчик открывается просто: в верхнем углу экрана нажимаем на шестерёнку, выбираем "сведения о системе", далее нажимаем большую красивую кнопку "Обновить". Ждём установки (довольно долго, минут 10), перезагружаем машину и всё работает. Надеюсь, что кому-то поможет.