1) Что если ещё раз aptitude install?
2) Что если попробовать в Синаптике поставить этот же пакет?
Пользователь решил продолжить мысль 16 Февраля 2010, 01:09:58:
Нет подходящей версии для ubuntu-restricted-extras
А с репозиториями что? Я не сталкивался с таким никогда, но что-то подозрительно. Я бы проверил флажки в Источниках приложений (вкладка "Пронрамное обеспечение Ubuntu" и "Обновления" тоже потыкать), снял бы, обновил и снова включил.