I just spent a couple of hours with the same problem using a 4x20 chars LCD. In my case the problem was that the LCD R/W pin was floating instead of being pulled low. I just tied it to GND and voila!, it worked.
Check this.
JM