Dois minutos, ou mais, não é normal...
1) Para tentar procurar por possíveis mensagens de erro durante o arranque,
Após ligar o computador, após o apito inicial e assim que surgir a imagem da BIOS, fique a carregar numa das teclas "Shift" até aparecer o menu de arranque (do GRUB) do Ubuntu. E, assim que aparecer tal menu, carregue na tecla "e", com a opção "Ubuntu" escolhida, para editar temporariamente as opções de arranque (e apenas para esse arranque).
Numa das primeiras linhas que aparecem, substitua "$linux_gfx_mode" por "text" (esta opção é capaz de ser desnecessária, mas não se perde nada em fazê-lo). E, depois disso - e mais importante - remova as opções "quiet", "splash" e "$vt_handoff", da linha que começa por "linux" (que é uma das linhas que estão quase no fim).
Depois de fazer estas alterações, carregue em "Ctrl+x", para iniciar o GNU/Linux.
(fonte:
https://wiki.ubuntu.com/DebuggingKernelBoot)
Vai ver uma série de mensagens, que começarão quase todas por "[ OK ]". E, se houver algum erro, deverá aparecer algo em contrário.
Sendo que, se algum procedimento, em particular, estiver a tornar o arranque (muito) lento, deverá conseguir ver o que se passa, por as mensagens pararem de passar todas muito rápido e pararem na mais recente - que deverá ser onde está o problema, Mas, se não...
2) Depois do arranque, pode usar (num terminal) o comando "journalctl -b0 --system _COMM=systemd" para ver algumas das mensagens do registo do seu último arranque - e prestar atenção às marcas das horas, para ver o que está então a demorar tanto tempo.
(fonte:
http://askubuntu.com/questions/763638/no-more-boot-logging-since-16-04)
Mas, relativamente a estes últimos comandos, não lhe sei dizer mais nada - por serem estes comandos novos, que nunca usei, e que são uma novidade que foi introduzida nesta versão mais recente do Ubuntu.
Essencialmente,
O que você tem de fazer (para descobrir onde está o problema), é fazer o Ubuntu mostrar as mensagens no arranque (processo que se manteve praticamente o mesmo) e/ou usar comandos que lhe mostrem as mensagens que ficaram gravadas no registo do seu último arranque (processo que foi alterado para a nova versão 16.04 do Ubuntu e sobre o qual poderá pesquisar na Internet).