I cannot believe I didn't notice this earlier. I have discovered exactly what the problem is. (EDIT: Then again, it could just be the result of a different problem, but it at least confirms that there is an issue.)
(Explanation of Gimbal lock: http://everything2.com/index.pl?node_id=1528097
This can be observed using my original example above. All you need to do is, quite simply, rotate Pitch to 90 degrees. At this point, Yaw and Roll achieve the exact same motion on the 3D Box. This means you have lost one degree of movement, and have achieved Gimbal Lock.
While this may not seem a big deal at first glance, this causes major issues when you start doing anything of complexity using the 3D Boxes. It is also a well known issue that extends beyond just 3d programming (Apollo 11 anyone?).
In case anyone is interested as to my 3D Rotation implementation, I have used the Axis Angle method (in a Matrix), courtesy of the following website:
http://www.euclideanspace.com/maths/geo ... /index.htm
Axis angle and Quaternions both, technically, avoid Gimbal Lock. Whereas Euler Angles are known to be plagued by it (though I make no assumptions that is the cause in this case).