I have also had this problem. And vask's solution seems to have worked, though with a slight modification; I did not create any new Skype account. Here is what I did: 1. Disable the Skype account which has the problem. 2. Using "xTerm" or whatever you like, and go to "/home/user/.Skype". 3. Delete the folder with the intended Skype account name, or just change its name. 4. Enable the Skype account again. All Skype contacts should come back alive again.