A discussão da barra de lançamento (link abaixo) tem várias sugestões que você pode encontrar para você. Supondo que sua causa é a mesma, suspeita-se que swap e / ou systemd sejam o problema. Tente estas possíveis correções:
sudo systemctl reboot
(funciona ocasionalmente para mim, mas não 100% do tempo)
sudo swapoff -a
ou até mesmo uma combinação dos dois
sudo swapoff -a && sudo systemctl reboot
Embora, quando eu testei isso, a parte de troca levou > 10 minutos de qualquer maneira. Para o desligamento, substitua 'reboot' por 'poweroff'.
Como uma nota lateral, eu tive esse mesmo problema no meu PC do Ubuntu 15.04 até o atual 16.04. É possivelmente ligado a quanto tempo o computador está em uso. Se já faz algum tempo, levará muito tempo para desligar ou reiniciar (10 minutos ou mais em uma tela preta ou tela com um cursor).
Eu descobri que esse problema relatou alguns lugares que você pode achar úteis: