Maybe after a reboot there aren't any users in your system, where without kicking them off they're creating disk i/o contention as well as lock contention during your index creations?

Either way, there's really nothing in a reboot itself that would decrease disk intensive processing time other than stopping/disconnecting other processes. There must be something else going on with the server during slower times...