Mine does take a couple mins if you count the time from pressing the button, to when the "busy" light stops flashing.....
But then, when it boots, it loads Zonealarm, AVG (which always does an update) logs into Gmail, boots up Peerguardian, SpywareGuard, Spybot and NetLimiter, and all of these connect too (and start scanning) but it's usuable (ie, open an IE window and go to PF or Gmail etc) within about 60-70secs or so....
Which ain't bad for what is basically, an old hat machine by todays standards. 2.8 P4 (only a 533mHz FSB and L2 cache) and is single core chip.... plus it has 2 HDD's to boot up, 2 optical drives, a third USB HDD ot read, and memory card/usb flash drive to read...
So not the end of the world.....