Why is Gimbal Lock an issue?

I understand what the problem with Gimbal Lock is, such that at the North Pole, all directions are south, there's no concept of east and west. But what I don't understand is why this is such an issue for navigation systems? Surely if you find you're in Gimbal Lock, you can simply move a small amount in any direction, and then all directions are right again?

Why does this cause such a problem for navigation?

I don't imagine that this is a practical issue for navigation any longer, given the advent of GPS technology. However, it is of practical concern in 3-d animation and robotics. To get back to your navigation example, suppose that I have a mechanical gyro mounted in an airplane flying over the North Pole.

If the gyro is only mounted on three gimbals, one of the gimbals will freeze because moving smoothly to the proper orientation would require at least one of the gimbals to flip 180 degrees instantaneously. The gimbal lock problem can be countered by adding a redundant degree of freedom in the form of an extra gimbal, an extra joint in a robotic arm, etc.

As you pointed out, it's the singularity at the poles of the representation that's the problem. Having a redundant degree of freedom helps because you can have enough information at the pole to move the correct direction. In 3-d graphics, if an axis-angle representation (Euler axis and angle) or quaternions are used instead of a triple-axis representation (Euler angles), then weird rotation artifacts due to gimbal lock are eliminated (performing a YouTube search for "gimbal lock" yields several visual demonstrations of the problem).

One problem that I have come across is when roller coasters are being designed. If you have the pitch at +/-90 degrees (pointing straight up/down) then using normal Euler-based orientation you can't easily specify an angle of banking as you have no reference to 'up'. To solve this Quaternions are often used.