Zdravím všechny kteří mají obdobný problém.
Skype používá ke všemu "zabugovaný" explorer, stahuje si přes to aktualizace všechno. Tudíž je ve vašem zájmu mít dobře nastavené připojení u exploreru. Skype přeci jen funguje, videohovory fungují vše jde, ale jenom přidávání kontaktů je problém. Hází to chybu špatného připojení. Přesně tak, máte špatně nastavený explorer, přes který skype vyhledává kontakty. Minimálně u mojí verze skype 5.10.0.116
Takže jsem "a teď to bude trošku pro laiky" spustil klasicky explorer, nahoře jsem si klikl na nástroje -> možnosti internetu -> záložka připojení -> nastavení místní sítě (platí i pro wifi připojení) -> zaškrtnout automaticky zjištovat nastavení, jinak všechno odškrtnuté (pokud jste někde na proxinách, musíte vyplnit správně váši proxinu) :D
Pokud vám nepomohlo ani toto, tak problém je vždy v exploreru. To znamená, že váš explorer(windows) není v kondici, protože se o něj nestaráte :) takže ho porychtujte a bude to OK :)