Typically one could start looking with an oscilloscope to see what the Vcc voltage looks like and possibly how you have the arduino and motor ground wires routed to the negative terminal of the power source, they should not share the same conductor anywhere and be connected together only at the power supply.
It can be solved but you have to have good tools to see what you are up against and what effect any changes you make have on the situation.
Lefty