Поскольку через синаптик и другие штатные средства в убунте это не восстанавливается, привожу другой рецепт.
Если у кого такие же сложности, делайте так:
sudo gedit /var/lib/dpkg/status
В файле удаляете всё, что связано с неработающим/мешающим пакетом.
В моём примере это mate-media-gstreamer.
Обязательно сохраняем файл!
Далее пробуете восстановить базу командой apt-get -f install, и если всё сделали правильно, то ответом будет что-то вроде:
Чтение списков пакетов… Готово
Построение дерева зависимостей
Чтение информации о состоянии… Готово
обновлено 0, установлено 0 новых пакетов, для удаления отмечено 0 пакетов, и 19 пакетов не обновлено.
Дальше можете удалять/устанавливать всё, что вам нужно через штатные средства.