Reading quadrature encoder
volatile long rawTacho[2];      // interrupt 0 &amp; 1 tachometers

ISR(MotorISR1)
{
    int b = digitalReadFast(8);
    if (digitalReadFast(2))
        b ? rawTacho[0]-- : rawTacho[0]++;
    else
        b ? rawTacho[0]++ : rawTacho[0]--;
}

ISR(MotorISR2)
{
    int b = digitalReadFast(9);
    if (digitalReadFast(3))
        b ? rawTacho[1]-- : rawTacho[1]++;
    else
       b ? rawTacho[1]++ : rawTacho[1]--;
}

void setup()
{
    pinMode(2, INPUT_PULLUP);
    pinMode(3, INPUT_PULLUP);
    pinMode(8, INPUT_PULLUP);
    pinMode(9, INPUT_PULLUP);

   attachInterrupt(PCINT0, MotorISR1, CHANGE);  // pin 2
   attachInterrupt(PCINT1, MotorISR2, CHANGE); // pin 3
}


something similar to that - it was extracted from bigger code so you will have read it and understand it as opposed to copy paste.

Update note: This is not complete in a pure form - the cpu doesnt tell you what pin had an interrupt - thus some underlying Arduino code figures that out for me, but it is fairly efficient, and I used it as is. Also if it is not obvious, this is reading encoders from 2 motors. 1 interrupt is assigned to each motor, the second phase of each is on a non-interrupt pin. Never lost a reading to my knowledge.

The problem with your code is probably the print in the interrupt as pointed out in a comment.