Verifique a hora / data do seu sistema. É um tiro longo, mas pode ou não ajudar.
Além disso, tente permitir todos os cookies e limpar tudo relacionado ao navegador, não apenas ao histórico. Por exemplo. cache, cookies, etc.
Isso acontece com todos os sites que exigem uma senha? Ou apenas Gmail e Facebook?