Аналогичная проблема, не работает новый центр приложений в 16.04. Запускаешь центр, выбираешь программу, нажимаешь установить, появляется надпись - ожидание. Все, тишина!
Система свеже установленная, все обновления поставил.
Подозреваю что центр не видит интернета!
Интернет(PPPoE) через стандартное меню настроить не удалось, настраивал утилитой pppoeconf.