Wenn die "untere" Zeile bei dir schwarz ist, sind die Anschlüsse dann zufällig auf der Unterseite? Bei nem uninitialisierten LCD sind normalerweise die ungeraden Zeilen "schwarz", d.h. Display liegt kopfüber da.

Ansonsten versuch mal, die Wartezeit VOR die LCD-Initialisierung zu stellen. Wenn beide gleichzeitig bestromt werden, fängt der AVR sonst mit dem Initialisieren an, wenn das LCD noch garnicht richtig hochgefahren ist.

"die anderen Datenleitungen auf 5V": aber nur D4, D6 und D7 oder?
Wenn das bei D0-D3 auch noch der Fall wäre, stimmt was gewaltig nicht.

Und die 7V liegen hoffentlich weder direkt am AVR noch am LCD an sondern nur am Spannungsregler.