Não foi possível encontrar uma maneira limpa de resolver isso, então fizemos uma reinstalação completa da vlc, com base em user2325513 ' s comentário da seguinte forma:
sudo apt-get purge vlc
Pesquisou arquivos contendo "vlc" em seus nomes usando
find / -name vlc
Excluiu todos os arquivos de configuração encontrados usando isto como
rm -r ~/.config/vlc
rm -r ~/.cache/vlc
Instalado vlc usando apt
sudo apt-get install vlc
Descobrimos que o vlc tinha sua barra de menu de volta!