What distro are you using? How old is it? Some things off the top of my head:
Make sure your using a journaling file system. Ext2 Can be quite slow when booting up when it does consistency checks.
Check your init scripts and disable things you don't use often.
Make sure that your kernel is built with the Preemtible (Low Latency Desktop) Model turned on.