Well I clearly know a lot less about circuit design than I thought. There's something wrong with this circuit, and I can't figure it out. Something about the power distribution causes the Arduino to freak out when the 12v supply is powered on and delivering power through the voltage regulator.
I've decided to cut my losses and replace the motor control portion of this with a prebuilt relay board so that someone else has figured out all that part for me. I just bought two of these boards which can be powered from the 5v off the Arduino, and controls 8 relays. https://amazon.com/dp/B00KTELP3I/?tag=apkdotcom-20
This will let me completely separate the power supply of the 12v motors from the power supply of the Arduino.