At the moment my laptop takes just over 2 minutes too boot up Ubuntu, I've been looking through the forums though and it appears that under a minute is a reasonable time. Apparently it could be my wireless card that is delaying the boot, this fix has been offered that I'll have to play around with tonight:

Edit /etc/network/interfaces and replace everything in the file with:

auto lo

iface lo inet loopback

Update: This worked really well, my laptop can now cold boot and be on the internet with Firefox & aMSN running also in around 1 minute 5 seconds, fast enough for me!