I had not realized until reading this post that the wobble of the axis would mean that north would be pointing at different stars. But, I had heard that a few thousand years ago the constellations loooked different because the stars are moving relative to each other...fast, I'd imagine that constellations made up of stars that are relatively close to us would change fastest.
Chris