Maybe you should try smaller-value pull-up resistors. Although most I2C devices can't sink much current, a PIC can sink 25mA easily. You could use 560 ohm pull-up resistors on each end if you had an extremely noisy environment or long wires.

Also, if your two devices aren't on the same PCB, could there be a difference in GND potential between the two devices?