Solução alternativa
Se a resposta acima não resolver o problema, a instalação da versão beta do Google Chrome poderá solucionar o problema.
apt install google-chrome-beta
Isso parece não para resolvê-lo (entrada preservada por razões históricas):
Eu tenho o mesmo problema e depurei algumas horas de depuração.
O meu problema está apenas relacionado com google-chrome-stable Versão 53.0.2785.101 (64-bit) no Ubuntu 16.04.
Quando eu faço login em um site, os cookies são definidos corretamente. Quando eu fechar o cromo, sair, entrar novamente, os cookies ainda estão lá e está tudo bem. No entanto, se eu reinicializar , os cookies desaparecerem e eu precisar fazer o login novamente.
Eu fiz algumas depurações (reinstalando o chrome, revertendo para a configuração padrão, começando com uma configuração limpa, tudo como sugerido acima, ...) e o bug persiste.
Eu instalei google-chrome-unstable Versão 55.0.2853.0 dev (64-bit) e tudo funciona bem (enquanto estável ainda tem o problema). Então, esse é provavelmente um bug de software do Chrome.
Minha "solução": use o firefox / chrome-unstable por alguns dias / semanas, aguarde a atualização que corrige o problema para se propagar para o google-chrome-stable.
A propósito, estou usando o ubuntu 16.04 (systemd) com dm mapper / cryptsetup que foi atualizado a partir de 14.04 e ainda não tenho 100% de certeza que minha partição crypt é desmontada toda vez 100% corretamente (apesar do fs está sempre limpo). @Novah, você tem uma configuração semelhante?
É setembro de 2016 quando escrevo este conselho. Se não resolveu dentro de um mês automaticamente, minha resposta está errada ;-)
Espero poupar você de muita depuração e frustração.