I have a portable design which use 2x16 LCD. The whole boards required 50mA. Initially I use 2 CR2032 in palleral to supply 3 V to the board. However, the LCD starts flickering.
I use bench supply to develop the system and I didn't notice the problem. Only after I switch the design to battery supply, the board doesnt work.
You didn't say if it flickers while updating the display or while a steady message display?
However, I faced a similar problem & it was fixed by adding 2 wires to the supply rails going to the LCD and adding soldering layer on the data lines between the LCD & controller.
You didn't tell the LCD type! some are power hungry!
Of course you don't have a backlight! don't you?!