What operating system is being used? Even though roaming profiles have been disabled, a very complex group policy might cause a slow startup while applying all the policies to the access token. Try booting up as a local user only, not on the network, and see how quick it comes up.
What is set up to auto load on machine start up? Do a CTRL-ALT-DEL and look at the task monitor to determine what processes (NT, 2K, XP) or programs (9X, ME) are currently running. A large number of load-on-startup programs will slow the system down. Reduce this to only the ones that are necessary.
One other thing, how many fonts are registered on the box? Try to keep the number of fonts on a box to minimal levels for quicker boot up. All font properties must be loaded on start up and if you have 300+ fonts, that takes some time.