Eu estava tendo o mesmo problema em 11,10 e eis o que resolveu meu problema.
Atualizei minha versão do Ubuntu Software Center com a última versão encontrada no site de criação diária do mplayer (eu pensei em assumir o risco, já que não estava funcionando de qualquer maneira).
Eu adicionei o repositório manualmente em um terminal como este:
sudo add-apt-repository ppa:motumedia/mplayer-daily
atualize as versões disponíveis
sudo apt-get update
Depois, fui para a GUI do Gerenciador de Atualizações (ela está no mesmo menu de onde você pode desligar o sistema e é chamada de "Software Atualizado") e selecionou todas as atualizações disponíveis desta origem (mplayer-daily).
Depois disso, o mplayer funcionou bem novamente para mim.
Isso pode não ser a melhor maneira de instalar atualizações, eu realmente não sei, porque sou praticamente um novato no Ubuntu, mas pelo menos funcionou.
Espero que isso ajude alguém.