Edit: I had to remove the folder /home/user/.Skype
1.Open terminal
2.Type "rm /home/user/.Skype" or "mv /home/user/.Skype /home/user/.Skype_bak" (both without the ""). The first one deletes the folder, the second one moves it to .Skype_bak (just as a backup).
3.Try to connect to skype. It should work. The deleted/moved folder will be created automatically by connecting to skype.