I just dug out the code I used when I tested my LCD a while ago. It's based on Mike Bramwell's code- I can't remember where that came from. It has this line, which I don't pretend to understand. I just used it as is and it worked...
LiquidCrystal lcd(8, 9, 4, 5, 6, 7);
I assume the order of those pin numbers is important. I see from your post, @knuckles, that you mention pins 4, 5, 6, 7, 8, 9 and wonder if you've got them coded in the order 4, 5, 6, 7, 8, 9 whereas it should maybe be 8, 9, 4, 5, 6, 7?
(But if you posted the code as suggested, we would know.....)