Foi resolvido! Se alguém enfrentar esse problema e nem mesmo estiver trabalhando com todas as soluções incluídas na pergunta. Basta pressionar Iniciar e pesquisar "Opções da Internet" e permitir todos os cookies.
Agora execute o Skype novamente. Eu realmente não sei como ele é diferente do IE: (
Espero que isso ajude os outros!