Joe S., How long is the cable from the LCD to the PIC? Do you have a scope? If so put the leads on the power lines from the +5v and the ground at the display and see if you can see any noise in the region of 100mv or so. If this is the case I would power the LCD with separate leads from the LCD to the +5volt source. Depending on the length of the cable you are using, if it is too long the data lines are seeing cross coupling and this is being interpreted as bad data. The maximum length of the cable should not exceed more then about 6 inches. i have had problems in the past with VFD displays that draw much more power. An LCD display shouldn't draw more then a couple of milliamps without the backlighting. Are you running the backlighting from the same cable as the LCD data cable? If so I would change it to seprate cables and run it directly to the output of the supply.

Dave Purola,
N8NTA