Io ho un sospetto: il tuo MEGA non regge l'assorbimento della retroilluminazione del LCD.
Ho un LCD seriale che dava problemi molto simili ai tuoi quando collegavo anche un Servo.
Quasi tutti gli schemi applicativi degli LCD non parlano di un "ingresso per alimentazione retroilluminazione", ma semplicemente "Anodo" e Catodo": questo vuol dire che occorre inserire un resistore per limitare la corrente dei diodi LED.
Puoi provare a togliere la retroilluminazione e vedere se i caratteri appaiono normalmente o meno (il display appare spento perché è a caratteri bianchi su sfondo verde o blu, ma illuminandolo lateralmente con una torcetta dovresti vederli).
Se è così, è sufficiente inserire un resistore il cui valore dipende da quanto assorbe la retrolliuminazione (l'ideale sarebbe saper quanti sono i LED, come sono collegati e la caduta di tensione su ogni singlo LED, ma i datasheet non forniscono questa informazione).
Ad esempio, considerando LED bianchi che hanno una caduta di tensione di 3V e che son tutti in parallelo (e non potrebbe essere diversamente essendo la tensione di alimentazione a 5V), su un LCD a 4 righe dovrebbero essercene 9 ed a 15 mA di assorbimento per ciascuno fanno 135 mA. Sul datashett, infatti, viene indicata una corrente max di 125 mA che dovrebbe essere limitata con un resistore da 36 ohm.
Dico dovrebbe perchè una brutta abitudine tutta "cinese" è quella di alimentarli direttamente confidando nel fatto che la sovralimentazione è tollerata (anche se dimezza la vita del componente ed aumenta la corrente assorbita).