Смотрите версию Skype которую вы ставите.
После какой-то очередной смены версии протоколы несовместимы (должно быть 4.3.0.37).
А ещё лучше - пользуйтесь WEB-интерфейсом Skype
Да, такое бывает и на виндах и на андроиде. Иногда мелкософт меняет протокол обмена, те у кого настроено автообновление, получают предупреждение об обновлении, те у кого обновление отключено в один момент просто теряют коннект с сервером и разлогиниваются, с виду это может быть похоже на неправильный пароль, но это именно потеря связи из-за изменения протокола.
Ну и редкий вариант - гденибуть какая прокся или нат блокирует трафик скайпа.