What are the difference between PIC24FJ256GB110 Rev 00004 & Rev 00003
The usual place to find the difference between silicon revisions is the errata sheet. For example the following document seems to cover that device:

PIC24FJ256GB110 Family Silicon Errata and Data Sheet Clarification

It appears 03h was the code for revision A5 and the code 04h indicates revision A6. However unless I've missed something looking through that I can't see any known issues addressed or introduced with A6 that are different to A5.

Presumably though something was changed and it certainly could be your problem. It might be worth asking Microchip what was changed between revisions, I've found them helpful and responsive in the past even if you're a low-volume customer.