What if you only updated the LCD immediatly after a timer interrupt... or if the timer INT is happening too frequently to get through one cycle of LCD update you may have to offload one of the processes to a second PIC.

This is probably evidence you are reaching the outer limits of what one PIC can do and keep all the tasks properly serviced.

How about using a small 12f683 to mark time via the elapsed timer INT and have it only bother the other Main PIC when enough tic's have passed that the main PIC needs to know about it.

something to chew on.