I have a similar issue with XP that seems to be network related. If I am attached to a network, then after entering my login details to XP, the machine hangs for quite some time before starting up. Sometimes it doesn't start up at all. BUT, if not attached to a network, startup is immediate. This only happens after a cold boot - hibernating or suspending does not have the same effect.
My solution (until the next time I install an OS) is to simply unplug the network cable before restarting.