I connected a 16x2 LCD to my Mega according to the pins used in your code, uploaded and ran your code with no changes. The display works fine, showing "hello, world!" in the top line (line 0) and the current millis/1000 in the second line (line 1).
If the software works one must conclude that there is a hardware problem. Replace the jumpers, maybe there is/are a bad one/ones.
Does the breadboard have split power rails.
The jumpers that bridge the splits were added by me.
Post photos of your setup, please.