Aparentemente, ao olhar, vlc-data
ainda estava instalado no sistema. Mesmo depois de correr:
sudo apt-get remove --purge vlc
e
sudo apt-get remove --purge vlc*
Nenhuma ideia do porquê isso aconteceu.
Eu então corri:
sudo apt-get remove --purge vlc-data
Em seguida, desabilitei o PPA para o VLC e instalei o do repositório padrão. Então eu reativei a fonte e consegui atualizar para a versão 2.0.3.