Could you run through the connections for the 20x4 LCD for me?
It can't be the connections because you are getting legible information on the display.
It could be an 'out of spec' display. There have been a few recent cases where the standard LiquidCrystal library does not work with these displays and the LiquidCrystal1.0 library does. This library was written for the 40x4 displays but it also works with the smaller displays. Start here --> Google Code Archive - Long-term storage for Google Code Project Hosting. and use the Downloads link to get the latest version.
Don