Arduino 16x2 LCD Black Boxes
I have done some Googling across the web and it turns out that this can be caused by a couple of things:


Incorrect wiring.
Wiring of LCD backwards (ie 1 to 16 and 16 to 1).
Faulty wiring (ie broken cables &amp; dry joints).
Incorrect initialization of the LCD.
Buggy software.
Damaged screen.


The LCD screen that you have is a based on the Hitachi HD44780 chipset. It is the most common interface for text-based LCDs. It can be identified by the 16-pin interface. I2C is the next most common interface and is distinguishable as it has a 4-pin (sometimes 5-pin) interface.

Lets assume that your screen isn't damaged. From the details in your question, it sounds like your contrast is working just fine. The list above can be shrunk to just 2 things: bad wiring and/or bad code. Lets eliminate both of those by using known working software and known working circuit.

Arduino has an LCD library with example programs. Details for this library, including a wiring diagram, can be found over at the Arduino site in the Reference section. I use these example sketches to test my wiring connections before I write my own program. I recommend using the Autoscroll example.


Schematic:

These diagrams are from the Arduino Autoscroll page. I highly suggest that you read this page thoroughly. 

The code can be easily uploaded into your Arduino, through the IDE, by going into File > Examples > LiquidCrystal > AutoScroll, then Sketch > Upload.
You should see the sketch print the characters 0 to 9 on the top line (with autoscroll off), then moves the cursor to the bottom right (turns autoscroll on,) and prints the characters 0 to 9 on the bottom line, but as it prints each character the display should move one to the left.

If you get this example program to work then you know that you have a working LCD and also that your wiring is OK as well.