bootchart というソフトがあります。
http://www.atmarkit.co.jp/flinux/rensai/linuxtips/812usebootchart.html
起動時のプロセスをグラフ化してくれますので、これでどこに時間がかかっているかを調べてみてはどうでしょう。
Ubuntu のリポジトリにありますので、apt-get で導入するだけで大丈夫なはずです。feisty では PNG へのレンダリングまで標準でやってくれていました。

# ちなみに起動時に DHCP のアドレスが取れないときに、三分くらい待たされた記憶があるようなないような。

mizunoさん、コメントありがとうございます。早速「bootchart」をインストールしてグラフを確認しました。
上段の「ＣＰＵ（ｕｓｅｒ＋sys）とＩ／Ｏ（ｗａｉｔ）」のグラフでは、１７１秒までブルー一色でＣＰＵ使用率が１００％？？最後の方でＣＰＵ使用率が小さくなり、ピンク部分が表れます。
これって異常ですよね。
グラフ上段のコメントでは、ＣＰＵはＣｅｌｅｌｏｎ2.00GHzとなっています。また、time：2:54と表示されており、起動に3分くらいかかっているようです。


　

ｓｕｍｉｙｏｔａさん、コメントありがとうございます.
起動画面とはUbuntuのロゴと棒グラフで進行状況が表示される画面でしょうか?この画面でしたら、今はでていません。電源スイッチオンでハードディスクのランプは点滅していますが、画面は真っ暗です。起動画面を表示するには、どうしたらいいのでしょうか？

えーと、おそらくusplashのバグです。

とりあえず/boot/grub/menu.lstのsplashブートオプションを外せば起動時間は短縮されるはずです。

https://bugs.launchpad.net/ubuntu/+source/usplash/+bug/61711

myss18さま、問題解決おめでとうございます。

蛇足ですがご参考までに起動画面の表示方法を・・・。いつも自分が参考にさせていただいてる『LinuxSalad』の記事です。

http://linuxsalad.blogspot.com/2007/10/ubuntu-710_21.html