Resolvi (em parte) o problema, após muita pesquisa. A sequência para resolução é a seguinte:
1 - No Synaptic, instale o programa
Bootchart. Ele faz uma análise do processo de boot e emite um log detalhado a cada inicialização, gerando um gráfico numa imagem PNG. Essa imagem fica gravada na pasta
/var/log/bootchart. O log dirá qual processo está atrasando o boot, e por quanto tempo.
2 - No meu caso, haviam 4 processos levando mais tempo que o normal. Pesquisando
(http://ubuntuforums.org/showthread.php?t=1474136&page=2), descobri que o vilão provavelmente era a porta IDE na qual o DVD estava conectado.
3 - Desconectei o DVD da placa mãe, e pronto! O boot que levava mais de 2 minutos, agora leva assombrosos 15 SEGUNDOS!
4 - Obviamente isso não é muito prático. Então, conectei o DVD novamente, e apenas desabilitei a porta IDE pelo setup. Quando preciso usar o DVD, habilito novamente a IDE pelo setup, e o boot volta a ficar lento...
Bem, agora vem mais uma pergunta...
Alguém sabe como evitar que o Ubuntu fique criando caso com o DVD durante a inicialização?