The battery might be strong enough, but there are wires and connections.
I hope you are not using a breadboard ? Those have sometimes bad connection.
The current of the motor could drop the voltage of the Arduino.
Did you connect the 5V battery to Vin, the DC power plug or the 5V pin?
Is that battery 5.0V ? or lower, like 4.5 V ?
The Arduino needs at least 6 or 7V, although 5V should not be a problem.
Was the second power supply also 5V ?
Or did you use a higher voltage at the DC power plug.
I would like to know how everything is connected.
Do you have a large capacitor ? At least 1000uF. Try to add that to the supply voltage of the motor, or the Arduino, or the PWM controller. If think it will make a difference.