What must be remembered is that evolution can proceed a lot faster than was previously thought. The best illustration of this is the Grant's study of Darwin's finches on the Galapogos Islands. They have studied in excess of 19,000 indviduals over 24 generations, and have observed wide evolutionary swings, tracking environmental changes. What has led to to the assumption of a slower rate is that, over time, these environmental changes tend to average out to a norm, so "snapshots" taken at longish intervals miss the changes.
So, given a permanent environmental change and a reasonably plastic genetic makeup, a species can "track" these changes.