LCD PC1602 16X2 display giberish

Yes, I know this issue is not new, but I am still having the problem, and would like to have some help, if possible.
I just connected a PC1602 LCD to Mega (as well as to Duelmilanove),, but I can not get it to show the text I am sending to it, and I read instead gibberish.
The connection and program are very basic:
LiquidCrystal lcd(7, 6, 5, 4, 3, 2); //Corresponding to LCD pins (rs, enable, d4, d5, d6, d7)
void setup() {
lcd.begin(16, 2);
lcd.print("hello, world!"); }
void loop() {
lcd.setCursor(0, 1);
lcd.print(millis()/1000); }

I used both USB and external PS, the voltage is kept stable at 4.85V (no noticeable noise)
To test, I used the built-in Arduino LCD example ("Hello Word" and timer)
The LCD is alive and active but showing gibberish (on right time, correct character positions).
I doubled checked the connections to make sure I did not mix up the lines, checked voltages and scoped the lines. All seems OK.
I have googled long and most issues I have found have to do with long lines, noise or low PS, but in my case, the showed characters are not randoms: They repeat exactly, which does not make sense with (random) noise.
What could be wrong? any idea? Is there any setting for characters set for LCD?
thanks.

You say that the gibberish that you see is consistent. What do you see on the LCD where hello, world! should be ?

Thanks UKHeliBob for the support.
While trying to read and copy the gibberish as you suggested, I found the problem as follows:

In my case, I use 2 digital pins to supply +5V and GND to the LCD (out of convenience only).

Unfortunately, in my setup I placed those two digital command lines after the lcd initialization, which means the LCD could not read the initialization command, and thus failed.
BY changing the order, I now get the correct text (another problem is the contrast, which for some odd reason requires negative voltage ....).
Thanks again
samtal