Se não for um problema com o tema que você está usando, você já tentou atualizar o cache de ícones com sudo gtk-update-icon-cache /usr/share/icons/hicolor ? (substitua "hicolor" por qualquer tema que você esteja usando. Você precisará colocar o ícone na pasta de tema apropriada também)
Como um pouco de informação extra. Em /usr/share/applications , você encontrará um arquivo vlc.desktop . Você pode alterar a seguinte linha:
Icon=vlc
Com outro ícone de sua escolha (eu prefiro definir um arquivo svg no diretório "escalável" em vez de um x rasterizado por y png). Depois disso, você precisa fazer o comando update que eu dei anteriormente.
Se você encontrar algum problema com o comando update, tente anexar as opções -f -t.