É difícil responder sem uma lista completa de pacotes no seu sistema e possível a saída do console que normalmente é ocultada pela tela de desligamento. No entanto, alguns bugs foram corrigidos no desligamento (eu sei, porque eu mesmo consertei alguns) que o tornam mais seguro para os seus dados. Muitos serviços não estavam sendo finalizados corretamente nas versões anteriores, o que às vezes resultava em corrupção do sistema de arquivos! 11.04 tinha algumas correções para isso, e 11.10, mais algumas. Eu não acho que nenhum dos novos métodos deva adicionar mais de 10 segundos ao desligamento.
Talvez aperte 'pgdn' enquanto desliga para ver se alguma coisa está sendo impressa no log de plymouth.