Most likely the motor is drawing lots of current at start-up thus it drains the cap on the 12V line and the system, so the regulator cant maintain a good 5V if the 12V is unstable...
simplest fix... get a BIG capacitor, a few hundred uF (470uf+ or 1000uf if its a bigger motor) on the 12v side...