Threshhold voltage typically falls with increasing temperature, which would seem to indicate that high temperature operating conditions should result in faster gates than low temperature OCs. However, standard cells typically have slower timing with high temperature, and faster timing with low temperature. What is the physical explanation as to why this is the case? I would guess that it has to do with the carrier mobility.
High temperature implies more thermal noise and random collisions of electrons, thus device resistance goes up and electron mobility goes down.
If resistance goes up then the RC constant(s) across the device nodes will be higher and speed will be lower, as speed is inversely related to RC.
edit: to address 2nd comment
(w/ respect to temperature effects)--
For digital applications, the change in threshold voltage is usually negligible compared to the mobility changes; that is, the mobility changing generally has a much greater impact on the propagation delay than does the threshold voltage.