Eu estava experimentando a mesma coisa. O problema é que a linha Exec=skype-wrapper no arquivo /usr/share/app-install/desktop/skype.desktop está errada. O executável skype-wrapper não existe. Se você alterar essa linha para Exec=skype , ela funcionará.
Eu abri o link para rastrear o bug .