Kan,
Vc deveria ter achado, ao menos, o pacote libdvdcss2. Mas aqui, pelo menos, apesar de listado, ele não está instalado. Verifique se vc tem instalados os pacotes libdvdnav4 e libdvdread3. Aqui eles estão instalados. Aqui vão as respectivas descrições:
The DVD navigation library
This is the DVD navigation library, which provides an interface
to the advanced features of DVDs, like menus, navigation, etc.
This package contains the libdvdnav runtime library.
e
library for reading DVDs
libdvdread provides the functionality that is required to access many DVDs. It
parses IFO files, reads NAV-blocks, and performs CSS authentication and
descrambling.
libdvdread currently uses libdl to dynamically probe for libdvdcss at runtime.
If found, libdvdcss will be used to decrypt sections of the DVD as necessary.
Abraço