I have had simular problem. although I managed solve it because the LCD i was using had a busy signal on the 8th bit when powering up (and if it was carrying out instructions.) i just polled the 8th bit until low (not busy) and then carryed on. the only other thing I could suggest is that the voltage supplied to your LCD is a little to low.