A alteração dos pacotes deb é um pouco complicada, já que você está simplesmente substituindo as dependências, às vezes isso funciona, mas não há garantias. O cano quebrado provavelmente virá disso.
Um caminho alternativo seria compilar a partir da fonte, muitas vezes um simples configure e make será suficiente, mas neste caso não funciona e será necessário um pouco mais de esforço para lidar com todas as dependências.
No entanto, a versão que você tenta instalar não é a mais recente, no sourceforge existe uma mais nova. se eu pegar uma nova instalação do 15.04, eu posso instalar isso sem nenhum truque apenas usando o software-center:
- faça o download do link
- abra com o ubuntu-software-center e instale
Parece que nessa versão a dependência do mencoder foi descartada.