Input change notification not interrupting after sleep()
This doesn't explain exactly what you describe, but could be relevant.  Remember that on most PICs (don't remember whether the PIC 24 does this specifically) the instruction following SLEEP is fetched and in the pipeline, therefore always executed as the first instruction after the processor wakes up.  This is true whether the wakeup condition causes a interrupt or not.  Often this extra instruction is harmless, but not if it messes with interrupt state.  To be safe, you can put a NOP immediately following SLEEP.