[Removed]
It can be quite common but the other way round. That is you can have trouble if the rise time of the power supply is not fast enough.
I have never come across the inverse.
Try powering it up while holding down the reset button and then releasing it. If this works it could point to the fact that you are trying to initialise the LCD too soon after power up.
I suspect your display module is not booting up as quick as your atMega 328. Try inserting a delay of say five seconds at the start of your setup funciton.
[Removed]