How to calculate phase shift between two square waveforms with Arduino DUE
With 0° you have two inputs triggering interrupts at the same time.  That can't happen.  You can't run two interrupts at the same time, so the second one gets queued up until the first has finished.

With all that serial printing in there there's going to be quite a delay between one interrupt triggering and the next one being allowed to trigger - giving you skewed results.

I would suggest passing your signal through an XOR gate so that you end up with a single small pulse that represents the phase shift between the two signals.