motor affecting time calculation between hardware interrupts
Noise from electromagnetic sources is always an important issue that must be addressed. The aims are to minimise noise generation at source, reduce transmission of noise between source and the "target" affected circuitry and reduce noise impact at the target. 

Motor controller circuit diagram here

The shield power supply link MUST have been removed.
Shield must have all own powering.
Coupling via a common eg 5V supply has a high chance of being problematic.
The two 5V supplies (arduino &amp; shield) could have a common higher voltage source but need separate regulators and proper noise removal in each supply. 

Placing extra capacitance across the arduino Vin or main power source MAY help.

I assume that the motors are driven in either direction during operation. If not then a reverse diode across the motors should help.
If bidirectional,  try reversed diodes from each motor lead to Vout (= V+ motor drive voltage).   

The shield's Vout filter capacitors C7 &amp; C8 care 47 uF each.
Vout could usefully have 1000 or so uF added somewhere on the board.  

I do not know how much motor current is drawn and exact control strategy. This MAY interfere with motor drive but probably not: Identify one motor which "has issues". Add a small series resistance in each lead with a capacitor across the leads on the motor side. Here "small" means "does not noticeably affect performance". eg 1 Ohm if Imotor &lt; to &lt;&lt; 1 amp. Capacitor needs to be biplar for bidirectional motor control - eg a 1 uF ceramic or plastic (polyester, mylar, ...) cap.

'If all else fails'[tm] opto coupling the driver interface is possible BUT should not be needed. 

Try above.
Report.
Ask more questions if needed.