Então, depois de muitos testes eu posso ter descoberto. Eu atualizei o kernel de 3.16 para 3.18 e então também instalei o driver mais recente da Nvidia que aparece no Ubuntu Software Center. Embora não seja o mais recente driver da Nvidia, acho que foi o meu problema para começar.
Eu também tentei instalar a mais recente Nvidia direto do site da Nvidia, mas eu só recebo erro após erro. Primeiro, ele me diz que eu não tenho a GPU certa para o driver, então eu tenho o servidor X runnig e, em seguida, algo relacionado a um script com falha.
Então, agora vou experimentar o Ubuntu como um louco e ver o que acontece a seguir.
ATUALIZAÇÃO - Vitória !!! - Driver atualizado da Nvidia resolveu meus problemas
Eu apenas reinstalei o Ubuntu (apenas para descobrir o que estava acontecendo) e, claro, o desligamento do desligamento / reinício reapareceu. Isso significava que eu poderia recriar o problema. Então, tentei reiniciar algumas vezes sem sucesso. Então, eu fiz uma atualização de software que instalou um monte de atualizações, mas manteve o meu atual kernel 3.16. E o desligamento e a reinicialização ainda não estavam funcionando. Fui então para Drivers Adicionais e atualizei o driver da Nvidia para o driver proprietário e testado. Reinicie e VOILA !!! Está funcionando bem. No final, o kernel 3.18 não fez nada para ajudar no meu problema!
Então, se você está tendo congela / trava no Ubuntu enquanto tenta reiniciar ou desligar, há uma grande chance de você estar tendo algum tipo de problema de driver!