caso você queira remover também os arquivos de configuração, use:
sudo apt-get purge ubuntu-restricted-extras
se você quiser manter os arquivos de configuração (porque você quer reinstalá-lo mais tarde usando a configuração antiga):
sudo apt-get remove ubuntu-restricted-extras