De acordo com o site oficial :
O VLSub não está funcionando com o Vlc 2.1.x em nenhuma plataforma porque a lua O módulo "net" necessário para interagir com o opensubtitles foi removido em esta versão para as extensões. Funciona com o Vlc 2.2 no mac e no linux.
Muito ruim o Ubuntu tem 2.1.x. Então, o primeiro passo é obter uma versão mais recente do VLC:
sudo add-apt-repository ppa:videolan/master-daily
sudo apt-get update
sudo apt-get install vlc
No momento da escrita, o plugin VLSub nos repositórios do Ubuntu (0.9.10-1) não procura legendas, e a última versão do GitHub tem problemas para abrir a legenda depois de baixada. Então, eu criei um fork que realmente funciona (testado no VLC 2.2.0 ~ git20140609 + r57027 + 123 ~ ubuntu14.04.1 e todas as versões posteriores, sem problemas até agora):
wget https://github.com/kraxor/vlsub/archive/master.zip
unzip master.zip
cd vlsub-master
Para instalar localmente, digite:
cp vlsub.lua ~/.local/share/vlc/lua/extensions/
Ou instale todo o sistema:
sudo cp vlsub.lua /usr/lib/vlc/lua/extensions/
E você está feito. Aproveite.