I also use the IDE v1.0 although these days I mostly use make for my compilations. I use the same LCD display as you.
I am not sure if I can help much as I haven't used this circuit with an actual Arduino for quite a while. I have moved on to using bare-chip AVR ATtiny85 and ATtiny84 designs. There is a video of my ATtiny85 version at 2-Wire Arduino Driven LCD - YouTube
I can say that without the bypass capacitors the circuit was unreliable, displaying random garbage, as you are experiencing. I could tell that the firmware was sane because I could send serial commands to the circuit to turn the LED on and off. Inserting bypass capacitors solved my reliability issues. If you insert bypass capacitors and still have reliability issues you may have power supply noise. Finally, substitute different physical ICs and display in case you have a chip problem.
Two pieces of advice that I have learned the hard way on this project. (1) If you use one of the ATtiny chips, pay attention to the core's pin assignments. There are several ATtiny cores out there and they differ. I use MIT's Arduino-Tiny core; (2) If you use a serial connection that uses a CP2102 I/O chip, isolate the Rx line (CP2102's Tx, your board's Rx) with a signal diode. Otherwise your circuit will lockup if connected during power-on - or appears to lockup as the LCD displays the same pattern as if no CPU were present. Oddly, if connected after power on it worked correctly. Anyway, diode isolation solved that issue.