I spent the better part of two hours struggling with your average HD44780 driven 16x2 character LCD, even though I was using the LiquidCrystal library that comes with the arduino environment. My problem was the text I was printing out looks like this:
I tried a lot of things, like adding in delays here and there, even going so far as to use a subclass of LiquidCrystal which inserts a 2ms delay after each write to no avail. Then by a process of elimination, I found that if I reverse the order in which the lines were printed, i.e. print line 1 then line 0, the problem goes away:
Whiskey Tango Foxtrot.