After investigating (which in my case meant briefly recalling from memory how PEAR actually validates dependencies), I remembered that PEAR validates dependencies twice, once prior to download, and once prior to installation. By the time the dependencies are sorted, PEAR assumes that the sort algorithm properly sorts things.
This is actually a pretty reasonable assumption considering the unit tests that are in place to test this. However, like all regression testing, the unit tests test boundaries and likely cases, but not all possible inputs.
So, to try to figure out where things might have gone wrong, Greg does a little research to find the problem. He discovers that it has to do with the order that the "subpackages" for the dependencies are installed, where the contents of those files are not removed correctly before installation, resulting in a file conflict.