Tudo o que você precisa fazer é ativar o software "Canonical Partners".
Basta abrir "Software Sources" no menu Unity, depois em "Other Software" e marcar a caixa de seleção "Canonical Partners". Depois de autorizar essa alteração com sua senha, atualizei meus repositórios no console:
sudo apt-get update
Afinal, você encontrará o Skype, mesmo como sugestão de software no menu Unity.