GPS gives weird characters when powering my ATMEGA328 on and off?
This is most likely caused by running the init routine switch the LCD from 8 bit mode to 4 bit mode when it is already in 4 bit mode.  It may be possible to try putting it in 8 bit mode and then switching back to 4 bit mode.  The most reliable solution is probably just power cycling the display as part of the init routine get it in a consistent state.