How much time are you allowing for the positive portion of the Enable signal? The data sheet I have for HD44780 controllers specify a minimum pulse length of 450ns for the positive portion and a minimum cycle time of 1 microsecond. The data lines must be stable when Enable goes low.
Also, the contrast on many LCD modules requires a negative voltage, around -3v.
When all else fails, give some thought to using a serial LCD interface IC, such as the EDE700 from E-Lab Digital Engineering. It has a built in diagnostic mode which will display a message on your LCD without any connection to your CPU.

Hal