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).