Cerca con pFind in Menu-Filesystem "skype" e vedi le directory dove sono presenti i suoi files. Ci dovrebbe essere un link in /usr/bin e di solito i files sono installati in /usr/share/skype con un desktop file in /usr/share/applications. Cancella tutti quanti. il link in /usr/bin, il desktop file in /usr/share/applications e la dir /usr/share/skype, e poi fai:
fixmenus
e restartX.