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
Chances are you have a common ground wire or ground loop or similar issue. Post a photo of your setup.
Can the motor supply drive the motor at full speed (ie directly connected, no transistor) without thevoltage falling below the nominal value? (ie is the power source up to the job?)Have you ensured _both_ power and ground wires to the motor circuit branch off before the 7805, that the 7805has suitable decoupling right next to it?