LifeHacker起動のシーンのムービがありますが、それ見る限り超早いです。
Ubuntu 9.04を18秒で起動させるの巻(SSD使用)
まぁSSD使ってるしBIOSもいじってるしOS自体もカスタマイズしてるそうなので、素のUbuntu9.04がどれほど早いかは不明ですがちょっと試してみる価値はありそうです。
ちなみに現在はUbuntu9.04はベータ版で、正式版は4月23日リリースらしいです。
最近Linux敬遠してる理由のひとつが起動が遅すぎって事もあるので正式リリースが楽しみです。
(ちなみに自分が現在使ってるWindows xpは起動にBIOS込みで40秒くらいかかってると思います。)