Ubuntu Lucid too slow to boot?

Check if you have FAT or NTFS partition...presence of FAT/NTFS partitions can cause 'fsck' to run at every boot causing significant delay in the boot speed. Following are the entries that I find in my /etc/fstab:
#            
proc            /proc           proc    nodev,noexec,nosuid                  0       0
/dev/sda1       /               ext3    errors=remount-ro                      0       1
/dev/sda6       /data           vfat    defaults,umask=007,gid=46      0       1

All you need to do is to change the last parameter value in the FAT/NTFS entries from 1 to 0. The last parameter indicates whether the system checks for the file system during boot. 

With this change, my system just takes 40.6 seconds to boot as opposed to 2 minutes 6 seconds earlier!

This is just one reason as to why the boot could get slow. In any case it is best to run the 'bootchart' tool that captures information on the processes run during the boot [just google to get more information on the bootchart tool]. 

You can also press the ESC key as soon as the Ubuntu boot screen starts... to know messages coming out of the boot.