Thanks for the latest couple of comments, especially Brad's. Although these PIC are extremely powerful and can be pushed a long way, there is a limit.
I did some testing with a logic analyzer where both channels were interrupting simultaneously with same-size pulses ... I'll have to do some more!
Our team has decided we will use quadrature encoders wherever possible.
For those that are interested, I have published the final encoder, measure, and wallclock code at
http://www.sunsys.net/frc
Mike