Você precisa saber o nome do pacote do qual o skype foi instalado. Digite o seguinte:
dpkg -S skype
Isto deve listar todos os arquivos instalados a partir de pacotes contendo a palavra skype. O nome no início da linha antes dos dois pontos é o nome do pacote. Depois de identificar o nome do pacote, você só poderá executar
dpkg -r package-name-here