Sky in the very far future / past Motivated by this question about a stranded submarine in the Jurassic I would like to know:

Is there anything remotely left of our current skyline if we go back or forward millions of years so that the stars rotating around the milky way covered a measurable distance ? I would expect that the proper motion of a star causes an irreversible drift out of the original position. Are there any stabilizing factors which may allow that some star configurations are still discernible ?
The sun still rises in the East and sets in the West. So you quickly identify the cardinal directions.

By observing the point around which the stars rotate each night you can find the altitude of the pole, which gives you your latitude. You can't find your absolute longitude, but with good time keeping you can find your longitude relative to your starting point. The planets are still in the same orbits. You might find that Saturn doesn't have rings (it's not certain how old the rings are) 

The Galaxies would still be in the same positions, The Milkyway, Andromeda and the Magellanic clouds are all visible. Many more with a moderate telescope, The Milkyway would look different, in detail, the LMC and SMC would be in different positions.

However, the stars in the background have all changed. There are no constellations that have not undergone radical changes. There would be no stars that you recognise: Stars are visible either because they are close (and so have a large proper motion) or powerful and short-lived. All the stars you know would either have moved, or not be born yet.