Abrir una terminal y tirar:
sudo apt-get install vlc-plugin-libde265
no sirve de nada si no agregamos previamente el repositorio, por lo tanto los pasos a seguir serían los siguientes:
sudo apt-add-repository ppa:strukturag/libde265
sudo apt-get update
sudo apt-get install gstreamer1.0-libde265
sudo apt-get install vlc-plugin-libde265
Esto funcionó correctamente en Linux Mint 17.2 y debería de hacer lo mismo en Ubuntu y derivadas.
Entradas relacionadas: