It does sound LCD or video driver related, reseating the chips/connectors and checking for dry joints is a good starting point for either. Actually, if the normal video output is good, I'd suspect the LCD driver/cable more than anything - because if the characters aren't being messed up there, whatever system is doing the screen compositing is still properly functional.
Good luck!