Atualização de 2017-11-15
Parece que o 4.3 é agora oficialmente morto e as seguintes instruções não vão mais instalar uma versão funcional do skype.
RIP Skype 4.3
Publicação original
Eu tenho o antigo (4.3) e o novo skype (5.4) (também conhecido como "skype for linux beta") e ambos funcionam. O novo tende a ter problemas com vídeo, então eu ainda uso o antigo principalmente. Acredito que o antigo modo de instalação ainda funcione. Trabalhou para mim pelo menos.
Edite depois de descobrir que skype não existe mais no repositório apt do parceiro do Ubuntu:
Parece que ainda está disponível em um link de download, mas pode não estar disponível por muito tempo.
cd ~/Downloads
sudo dpkg --add-architecture i386
sudo apt-get update
wget download.skype.com/linux/skype-ubuntu-precise_4.3.0.37-1_i386.deb
sudo dpkg -i skype-ubuntu-precise_4.3.0.37-1_i386.deb
sudo apt-get install -f
Eu apenas tentei em um computador com o Ubuntu 16.04 e ele foi bem instalado. Ignore os erros que podem aparecer depois de executar sudo dpkg -i skype-ubuntu-precise_4.3.0.37-1_i386.deb até você executar sudo apt-get install -f (o que corrige os erros de dependência)
O crédito vai para esta questão
