After upgrading to MacOS X 10.1.5, booting time went up enormously (some others have noticed this, too). I saw a smiling Mac on a grey screen for two or three minutes, my hard disk spinning and making searching noises, etc.. After that time, everything reverted back to normal (boot process continued).
I didn't find any solution for this in the places I looked on the net, but somehow it occurred to me that it had to do with the filesystem.
What worked for me was Alsoft DiskWarrior. This magic tool sorted out every problem there was and now boot time is even faster than before. Before formating your HD give DiskWarrior a try - it worked for me!
Mac OS X Hints
http://hints.macworld.com/article.php?story=20020620232055689