The short version is I have an IK setup on my rig. The legs work mostly okay, except for the knees. The knees will NOT bend to find a solution to the IK problem. The arms, set up in a similar way, will bend correctly at the elbows to find a solution.
If I lift the foot pad goal up slightly, the knees will NOT bend. However, if I change the constraints on the knees and allow them to bend backwards, they WILL do that to solve the problem. They won't bend in the correct direction.
I thought this might have something to do with the rotation of the bones, so I tried rolling them with no luck. I tried adjusting the position of the knee pole, but that didn't help either. I can't seem to figure out why the IK solver is so opposed to bending the knees to solve a problem. The issue happens on both legs.
I do have a small bend in the knees, so the related issue (Similar issue: IK-rig doesn't bend when I add elbow-target/elbow-pole) doesn't seem to apply. I can't share the .blend file yet, but I'm working on getting permission.
EDIT: I've tried every permutation of rolling the bones, changing the pole angle, and knee bend limit.
The Leg Setup:

Leg Setup with Axes Showing:

Solution Not Found:

Visible Constraints in the Knee:

Relaxed Constraints and the Bad Solution:

EDIT: Adding emphasis.
EDIT: Adding more images.
If I turn off the knee constraints, leaving only the pole bone, the hip twists backwards and the knee points away. That might seem like the pole rotation is wrong, so I tried reversing it... (See next picture.)

When I reverse the pole angle, the hip twists around 180 degrees to compensate. The knee STILL bends backwards, but points towards the pole.

The chain length of three was correct for an IK constraint on the foot. The chain length of two is correct for the IK constraint on the shin. As for why the three-length doesn't work, well... Perhaps some day we'll know.
Thank you to everyone that commented.
– Joseph Catrambone Jan 27 '15 at 21:11