I think those LCDs have two driver chips (one for each lot of 8 characters) so it looks like one of the driver chips is malfunctioning.
I have been trying to push around with my finger to fix any loose connections.
I built my first LCD project yesterday and i had a simular problem, it turned out to be loose wiring.
Nicks diagnosis is probably correct (except each driver deals with 16 characters) ...
If it wasn't making contact properly ... it could show that same type of display