Fazer login no web.skype.com corrigiu esse problema para mim e para outras pessoas. Depois você deve poder logar via pidgin. Acredito que isso reconfigura o token e, ou quando a verificação de segurança for concluída no web.skype.com, ele não bloqueia mais o pidgin.