[Eakdrazile]

Вы можете указать точно ссылку, откуда брали образ установочного DVD (чтобы хоть глянуть, что там внутри)?
Обычно для воспроизведения DVD достаточно нескольких библиотек (типа libdvdnav, libdvdcss, libdvdread и т.д.) "движка" (xine, gstreamer и т.д.) и плеера, основанного на этом движке. Если вы используете плеер, основанный на gstreamer'е - там обычно очень длинная цепочка зависимостей, которые надо доустанавливать, чтобы всё работало - вполне возможно, что некоторых этих зависимостей просто нет на установочном DVD.
Попробуйте установить какой-нибудь альтернативный плеер (на установочном DVD их должно быть несколько на выбор). Поищите что-нибудь, основанное на xine (там обычно маленькие зависимости), или на mplayer'е, например smplayer.
Если на установочном диске был пакет UBUNTU-RESTRICTED-EXTRAS, но отсутствуют нужные для его установки зависимости - недочет команды ubuntu.
Может ненайденный файл это не "жёсткая" зависимость (т.е. обязательная для работы), а некая опциональная. В настройках Synaptic можно снять галочку "рассматривать дополнительные зависимости как обязательные", и тогда вся цепочка зависимостей уменьшается раза в три - ставятся только действительно необходимые для работы программы пакеты.