O arquivo .so que existe, mas foi relatado como "não existe" porque era incompatível com a arquitetura do sistema. Era uma versão de 32 bits, mas você tem um sistema operacional de 64 bits. De acordo com a documentação no site da Skype, existe uma solução simples.
Abra um terminal (ctrl + alt + t) e execute
dpkg --add-architecture i386
apt-get update
apt-get -f install skype