fm:
Give it a shot with a 2K2 resistor and check how the LCD is grounded. If you have long lead going to the LCD you may have added too much capacitance to the line and a 4k7 may be a bit too much. How long are your wires going to the LCD?
Do you have other i2c devices connected?
I've had this cabled up with 40cm leads for the power pins (one 20cm female-female and one 20cm male-male combined into a 40cm male-female) with the leads going to the ground and +5V rails on a breadboard. From there I'm using short (~10cm) breadboard wires to the +5V and GND pins of the Arduino.) The SDA and SCL leads are 20cm from LCD to breadboard, and 20cm from breadboard to Arduino.
I've now replaced the leads with single 20cm male-female leads and connected them all directly to the Arduino, and the counter's now going for about a minute before the display corrupts, so it looks like I'm on the right track with this.
I've also tried 2k2 and 4k7 pullup resistors, where the wiring is: 20cm lead from LCD VCC to breadboard +5v; 20cm lead from LCD GND to Arduino GND; 20cm SDA and SCL leads from LCD to breadboard and from breadboard to Arduino; resistor from breadboard signal to breadboard +5v. This gives about the same result as above, i.e. the counter runs for about a minute before the screen corrupts.
I don't have any other I2C devices connected at the moment. I do have a DS1307 RTC that I'm planning to use with this project and seems to function correctly in the test sketches I've used with it, i.e. I can set its clock and sync to its clock.