"Why did they recommend an opamp with such a truncated common mode input range?"
I think that's a fair question to ask Microchip. Their App Note shows a possible output of up to 5.0V with this configuration. The supply voltage is only spec'ed to Operational Max of 6.0V with their specification table only holding up to 5.5V. The maximum Vcm in the Electrical Specifications table is VDD-1.2V @25C, and I think that number will get worse with increasing temperature.
For this circuit, the highest output (and thus input) is needed for cold temperatures, where the common mode loss is not as bad. With 6.0V supply, and possibly 5.5V, it might have actually worked. But, for it to work, you really need a high supply.
I would ask Microchip what supply voltage is required for the opamp, since it's not specified in the App Note. They probably will take the easy road out and say "maximum", but at least you'll make them think a bit.