How fast is the encoder turning?
Even in assembler there is a limit in the speed a PIC can respond.
As a suggestion, try to put the LCD commands inside your ISR handler. If they are executed within the main, lot of time is wasted with no reason. If you don't move the encoder, LCD will still be accessed.
Ioannis
Bookmarks