Hi,
According to the manual the WRITE command "is self-timed and may take up to 10 milliseconds to execute on a PIC MCU".
I suspect that's the issue, most encoders produce a full quadrature cycle, ie 4 edges (4 interrupts) per click/detent. IF the WRITE operation takes 10ms (and/or you have that Pause 100 in there) it's likely that it will miss pulses/edges and get confused.

Try commenting out the Write operation and see if that fixes it.

Yes, that's what's I'm saying regarding New_Bits = Old_Bits.
At the beginning of the ISR you do New_Bits = PortA & %00000011 so the top 6 bits of New_Bits are cleared. At the end of the ISR you assign the value in New_Bits to Old_Bits so the top 6 bits in Old_Bits will also be zero. Therefor the second AND operation is unnecessary, but it doesn't have anything to do with the actual problem....

/Henrik.