Try using an external 3.3 volt source for the display and keep all grounds tied together. Depending on the LCD, it may be drawing too much for the 3.3v from the Arduino directly, giving you unstable readings. Although this display is specified to operate at 3.3V, you should still be able to use it with 5VDC if you don't have any other option. And also, you never want to apply/disconnect power to the LCD with data being sent to it over the data lines....could ruin it 
Also, like Anachrocomputer mentioned, (and I would try this first before the other power supply option) you need a contrast pot on pin 3. Hook up around a 10K pot with the outer legs between Pin1 (ground) and Pin2 (VDD) and the center pin of the pot tied to Pin3 (VO). Refer to page 6 of the manual and it shows the connections for the contrast: http://www.sparkfun.com/datasheets/LCD/ADM1602K-NSA-FBS-3.3v.pdf