Desculpe se estou atrasado para responder a esta pergunta. Mas eu encontrei o culpado nesse meio tempo. Foi o novo driver para a NVIDIA que estava causando problemas. Então eu mudei para usar drivers NVIDIA proprietários usando este (por me apenas a opção PPA funcionou - a primeira opção deixou meu sistema preso antes de login e, a única maneira de recuperá-lo para o desktop foi purgar todos os drivers nvidia e começar de novo).
Depois disso, mudei para o Intel Onboard Graphics usando apenas nvidia-xconfig e não houve mais congela na reinicialização do sistema após o reinício.