Hi Alx,
If you're using PBP's built in interrupt then yes, the LCDOUT can make it loose counts. PBP way of doing interrupts is to always finish the current command and THEN jump to the Interrupt handler. Depending on how much info you're writing to the display the LCDOut statement may take several milliseconds to complete.

Moving to an assmebler based interrupt handler will probably fix you up but an easier way, if your not that familiar with assembler is to use Darrel Taylors Instant Interrupt routines. Do a search on the forum and you'll find it. It will let you write your interrupthandler in Basic without the limitations of PBP's way of handling the interrupts and is very easy to setup and use.

Another approach might be to switch PIC to a 18F2431 for example. It has built in hardware counter for quadrature encoders so you don't have to keep track of with software.

Hope it helps.
/Henrik Olsson.