Para isolar o problema, eu diria começar no firewall. Até onde eu sei, o Skype usa a porta 80 e a porta 443. Então, primeiro, eu desligaria o firewall, se ainda não funcionasse, então poderia ser isolado para talvez um agente antivírus. Tente desativar o agente também. Se você o isolou no firewall, apenas permita que essas portas passem.