Its lame but I read a post where they suggested setting all of the exchange services to manual and then back to automatic. It looks like this worked, maybe it somehow reset what order the services were starting.