Não. Removido o Mplayer, por exemplo, todos os decoficadores (codecs) e bibliotecas instalados como dependências deste aplicativo serão mantidos. Evidente que o mesmo ocorrerá com os decodificadores de instalação independente, como é o caso do famoso w32codecs.
Aliás, a remoção de qualquer aplicativo via apt-get não remove as respectivas dependências. Para livrar-se de dependências desnecessárias, instale o programa deborphan (sudo apt-get install deborphan) e depois digite deborphan num terminal qualquer. A lista resultante deste comando indicará as dependências desnecessárias (é provável que, dentre estas, estejam indicadas algumas bibliotecas e codecs de som e vídeo; um conselho: não remova tais pacotes).