I just watched Paul's Youtube video showing a test of his encoder library, and at the rotation speed he uses performance appears to be perfect. Are you turning faster than that? But of course he's just servicing one encoder, not two.
In theory, the processor's serial peripheral should be able to handle serial coms independently from what's going on elsewhere, at least with respect to transmitting a single byte. Once started, it should continue to transmit right through any interrupt that may occur. So, again in theory, serial should not interfere with the encoder interrupts, and the interrupts should not interfere with serial. But that doesn't take into account what the serial library may be doing. Could you test this by having the Teensy keep track of the encoder positions, but only transmit it every 10 seconds or so? That would at least test whether the Teensy and Paul's library can handle two encoders.