Pretty weird.
I guess you might want to make some custom routines which split and position your string without you having to think about it. That is, if the problem really can't be solved just by some initialisation specific to your device.
What LCD display are you using? Got a link to the datasheet?
Did you ever try the display with the standard 8-bit Arduino LCD library? It'd be good to know the same behaviour is exhibited there.
Also, please let me know what I can do to improve the "getting started" experience with the 4-bit library. You mention you had some wiring problems. Feel free to add explanation to the 4-bit LCD library wiki page.
neill