Are you using the internal oscillator on the PIC? Might not be as stable as you think...
Also, try adding some CHAR_PACING (it's in the manual)...at 9600 baud, 5ms should be more than enough to keep a serial LCD happy.
Past that, try bumping down to 2400 baud and see what happens...