Is it correct you power up the LCD directly?
The method I use since recently is to wait at least a second (after startup), then power the LCD through digital I/O, then also wait the period mentioned in the manual before initialization.
Well it's different if you use a library, or if you do it all manually. It's not that difficult by the way.
Your connections seems to be correct and you wrote that you checked them using a multimeter.
About the LEDs + 4.7k Ohms, I use high brightness LEDs, they still can be used with 4.7k and this has no impact on the LCD I/O.
Slowing down the MCU simply means to choose a different clock frequency (some new PICs have internal oscillator which can be selected via software even after startup). Doesn't Atmel MCU too have internal 8 MHz oscillator?