I have the exact same problem as you, and its frustrating me to death at the moment. I have rewired several times, and at the moment I am even using a 'breadboard' just so I dont have to keep soldering and desoldering stuff
I have the 1st and 3rd lines all black, backlight and contrast work perfectly. I wired mine using this article:
http://www.myrolypoly.com/lcd_project/lcd_project.html
I have tried several other hd44780 displays, including another 4x20, as well as 3 1x16, and I get the same thing with all of them - only the initialization screen. I have also tried this with 3 different computers, 2 of which are Windows XP pro, and my laptop which runs Windows 98 SE. The only thing I can possibly think of now is that the LCD is simply not getting data from the computer. I am using a ribbon cable, about 2' in length to connect the LCD to the serial port. I am thinking that its either picking up interference, or just isnt carrying a strong enough signal. I am about to rewire yet again, using a quality parallel cable with EMI and RF filters on it. Any suggestions?