Quaternions don't experience gimbal lock. That was part of the reason they came into such wide spread use (that and they produce smoother rotations around arbitrary axies).

http://www.gamasutra.com/features/19980703/quaternions_01.htm

"Towlie, you're the worst character ever." I know...