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.