In my program I am using a skeletal system to represent characters. Each entity consists of a variable number of parts that can rotate around the 3 axes while possibly based on a source part which can be based on another, etc.

However, I am having major issues when combining rotations on different axes. For example, rotating a forearm part horizontally(yaw) while it is at a 90 degree vertical angle(pitch) in relation to the bicep part which is 90 degrees vertically down from horizontal should be different than the same forearm rotations while the bicep part is horizontally aligned.

That is not even considering possible roll angles in any parts, and I cannot simply use transformations(I think), because I need to keep coordinate records for individual parts.

I thought that maybe the order in which I was performing transformations was the problem, but I can't seem to find an ordering combination that works. Does anyone have any suggestions as to what else I should try? It really is getting embarassing now as I realy first started working at this problem around mid 2008, but education and what not have been interfering...

I'm sorry if you've heard this before, but I think skeletal systems are one of the major areas where quaternions really excel: http://en.wikipedia.org/wiki/Quaternions_and_spatial_rotation

If nothing else you could continue to store things in matrices or Euler angles and just convert into/out of quaternions when performing the operation which is causing problems.
http://en.wikipedia.org/wiki/Conversion_between_quaternions_and_Euler_angles

I was told that one of the main problems that using quaternions over euler angles solves(or improves on) is gimbal lock, and that one of the main problems with using them is uncertainty about exact angles.

I'm using a frame based animation system so theoretically I should be able to manual avoid gimbal lock(haven't noticed a problem yet), and I definitely need to know exact angles. The only reason that I'm not just making each parts' angles completely independent and just manually adjusting each is to make dynamic animations possible (or easier).

Also, wouldn't I still run into the problems with multiple parts and multiple axes(well the equivalent forgetting axes)? I was not realy having problems calculating rotated locations, it's just that I don't know how to combine them in a naturally looking way. or is that another pro for quaternions? I still don't understand them fully...

I'm not really sure how rotation matrices work...the OpenGL transformations use rotation matrices, correct? I need to read up more on these topics...

It's not about the uncertainty of the angles of rotations when using quats, but the fact that they are not immediately visible(as opposed to eulers, which are too easy, and matrices where the rows/columns represent the local coordinate frame's basis vectors in it's parent space). Quats really excel at animation due to the ease of interpolating between 2 frames(like key frames), or 2 different animations entirely(like blending walk and crouch to make a stealth walk)