From the code in @cattledog's post #5 it appears that the encoder update is polled rather than interrupt driven. Have you ruled out using interrupts?
I'm do not use the library Encoder.h, but my understanding is that if you supply the instantiation with two external interrupt pin numbers it will use interrupts.
Encoder encoder(2, 3); // Interrupts Pins
How do you determine a full rotation?
That specs you linked for that encoder show that there may be an index pin (Z) output. What encoder counts do you see back and forth between index pulses?