Hi,
First order of business, remove the Pause 100 from the interrupt service routine.

Also, is the intention really to write the MotorRPM variable to EEPROM on every interrupt? I see two possible issues with that, the first is that the write operation takes a while and the second is that you may wear out the EEPROM. Finally, not related to the actual problem but still
Code:
IF (New_Bits & %00000011) = (Old_Bits & %00000011) Then DoneRotEnc
Since you're assigning the value of New_Bits by ANDing PortA with 3 and then, at the end setting Old_Bits = New_Bits there's no need to AND New_Bits or Old_Bits with 3 here as well. Neither of those variables will ever have bits 2-7 set anyway, you've already taken care of that. (As long as you don't use them anywhere else in your program of course).

/Henrik.