No site do Skype baixe e instale a versão Ubuntu 12.04 (multiarch).
Vai baixar o arquivo skype-ubuntu-precise_4.3.0.37-1_i386.deb
Instalei na versão 16.04.1 usando os dois métodos e ambos funcionaram.
1) Instalar usando Ubuntu-Software
Nesse caso irá usar a interface gráfica da "lojinha" do Ubuntu.
Supondo que tenha baixado para a pasta Downloads, click com o botão direito do mouse sobre o arquivo .deb baixado e use a opção "Abrir com instalação de programa"
Isso irá acionar o Ubuntu-Software, então é so clicar no botão Instalar.
A instalação foi bastante demorada, dando inicialmente a impressão de que não estava ocorrendo, porém terminou e funcionou normalmente.
Entretanto, a desinstalação usando a própria central do Ubuntu-Software não funcionou, foi necessário desinstalar por linha de comando.
2) Instalar por linha de comando
Novamente supondo que tenha sido baixado para o diretório Downloads.
Numa janela de terminal:
cd Downloads
sudo dpkg -i skype-ubuntu-precise_4.3.0.37-1_i386.deb
Instalou e funcionou sem nenhuma dificuldade.
O pacote instalado passa a ter o nome simples de skype
Então, para remover:
sudo dpkg -r skype