I had the same problem and the easiest way I found to fix it was:
1. Log in to your Skype app
2. Go to Settings via the Menu button
3. Open the "Sync contacts" option
4. Select "Don't sync" and continue.
Everything should be just fine after that. Hope it helps!