Bem, parece que seus DVDs estão criptografados. Nesse caso, instalar os pacotes restritos não ajudaria. Você também precisa instalar o libdvdcss para reproduzir DVDs criptografados. Execute isso no terminal:
sudo /usr/share/doc/libdvdread4/install-css.sh
Lembre-se também que você precisa ter o libdvdread4 instalado antes de executar o código acima. Você pode não precisar instalar o libdvdread4 já que você já instalou o ubuntu-restricted-extras. Uma reinicialização pode ser necessária após a execução do script. Para obter mais referências, consulte: RestrictedFormats / PlayingDVDs