Primeiro você tem que identificar a causa, então um bom lugar para começar seria os arquivos de log (eu sei, não é tão fofo :), mas veja o /var/log/boot.log primeiro
Então você pode instalar o bootchart (sudo apt-get install bootchart) para encontrar onde ele espera e por quanto tempo. - depois de instalar o bootchart você precisa reiniciar.
A informação que você postou é um pouco "genérica" e difícil para qualquer um dar uma solução exata (se houver).