Last summer, for another answer on Worldbuilding, I wrote a script in an attempt to show how the positions of stars in the sky would change from the perspective of an observer outside the Solar System, using data from three catalogs: the Hipparcos, Yale Bright Star and Gliese databases. (The site which generated the CSV file I used is currently down, unfortunately.) As an example, I showed what the well-known constellation Orion looks like here on Earth and what it would look like if I traveled 10 (33 light-years) parsecs in the direction of $\alpha=0$ and $\delta=0$, where $\alpha$ is right ascension and $\delta$ is declination.
(I strongly suspect I made some numerical errors with the precise locations of the stars in the sky, but it seems that relative to one another, they're fairly accurate - and relative position is what's important here. The axes' scales are a bit off, so ignore the precise values for now.)
Here's Orion as it looks from Earth:
Here's Orion as it looks from 10 parsecs away, in the specified direction:
The constellation as a whole seems to have shifted slightly, but some stars in particular have moved more than others relative to the new constellation. For example, on Orion's belt the middle star, Alnilam, has moved away from its companions because it's further away. Mintaka and Alnitak, being closedrto Earth, have shifted more and therefore remain together. Bellatrix, too, has moved significantly because it lies only 250 light-years from Earth, much closer than any of the other stars - now it appears to be where Orion's other shoulder was, whereas that star, Betelgeuse, is off the screen.
It makes sense that we'd seen changes in Orion. 10 parsecs is a few percent of the distance to some of these stars (around at least 4% for some), and given the variations in how far away they are, that does make a difference. Added to that is the fact that Orion is close to 90 degrees in the sky away from the direction we're traveling - had we moved in the direction of Orion, I'd guess there would be less distortion.
To maybe quantify this a bit: Say we have a star a distance $d$ away, and we move $x$ distance in a direction perpendicular to it. For $x\ll d$, we see that it should appear to shift by an angle
$$\Delta\theta\approx\frac{x}{d}$$
Therefore, the angular shift of a star twice as far away than another will be half the shift of the closer star. Therefore, we'd expect Bellatrix to move five times more than Alnilam, which is roughly five times as far away.
Now let's say we're moving directly towards or away from the constellation. If the stars were all the same distance $d$ away and were separated by no more than a spatial distance $D$, the constellation would appear to have an angular size
$$\alpha\approx\frac{D}{d}$$
At our new distance, $d+x$, the constellation would have a new angular size
$$\alpha'\approx\frac{D}{d+x}$$
If the stars are at different distances, then their angular distances from the axis of travel will change individually by the above formula, with closer stars moving more and farther stars moving less.
I think that Orion is somewhat representative of the changes we'd see. The constellations in the sky don't involve stars which lie terribly far away because then individual stars would be too dim! Therefore, I'll handwave a little and say that traveling, say, 50 parsecs would be enough to render many of the constellations in the sky unrecognizable. Constellations perpendicular to the direction of travel would be completely unrecognizable; constellations along the line of sight might still be recognizable.
