Using separate power supplies solves the problem, but I'm eventually going to need to use only one power supply, so I'd rather fix the problem.
I purchased one of these opto-isolators from SparkFun, and hopefully that will do the trick? :
The reason I originally replaced the diode is because it only handles one amp, and in my previous circuit, using the Vin to power my motors was pulling 3 amps through it.
Zoomkat - Why do you recommend putting a cap between 5V & ground?
MarkT - Are you suggesting that the MOSFETs I'm using could potentially be generating a magnetic field and interfering with the Arduino because they're too close?
Thanks for the help, it's much appreciated!