I think you are right there, i have a same set-up at home (arduino uno, same model lcd) and that is also temperamental with exactly the same fault. I don't have any different LCD's to try I don't think, although I may have a serial display at work that I could possibly look at.
what kind of additions to the code do you have to put in to get your screen to work?
thanks for your time by the way 