I still keep my point. I think is a problem of soldering. Or in the soldering of the LCD to the board of the shield or if soldering of the header to the board of the shield or even of the header to the board of the Arduino.
EDIT: I even add something more. If is a problem in the soldering joints, the problem will be in one of 6 pins: E, RS, D4, D5, D6, D7.