De forma mais direta, experimente acrescentar na command line do menu do grub, a tela inicial de carga do sistema (coloque no final, após o que tiver na linha):
reboot=b
Fica algo assim:
linux /boot/vmlinuz-2.6.35-28-generic root=UUID=3efb2b68-0828-486f-8175-c63373391fee ro splash reboot=b
Caso funcione e resolva o problema, torne permanente alterando o arquivo /etc/default/grub
Uma discussão mais detalhada sobre o assunto:
[Resolvido] Travamento versão 11.04 ao desligar ou reniciar
http://ubuntuforum-br.org/index.php/topic,83031.0.htmlE ainda:
Ubuntu 11.04 64bits com dual boot não desliga [resolvido]
http://ubuntuforum-br.org/index.php/topic,85532.0.html