Tente remover o pacote completamente com o seguinte:
sudo apt-get purge skype-bin
Então, clique aqui , mas em vez de fazer o download Skype, abra-o com o Ubuntu Software Center. Instale-o de lá e aceite quaisquer avisos. Isso deve cuidar de dependências para você. Se falhar novamente - comente aqui com detalhes.