Powering a 6V motor from a 5V USB battery pack
I had a similar problem using a Pololu boost regulator to drive a motor. Placing capacitors before and after the regulator made the problem worse. The regulator drew a lot of power but failed to reach the full output voltage.

My conclusion was that the high initial load caused the bench power supply current limit to kick in, at several times the expected working current. This caused the regulator input voltage to drop within 5-10 ms of start. I assume the regulator at this point would work even harder to compensate for the voltage drop. This apparently ruined some feedback loop of the regulator, putting it in a locked-up state even though the steady-state power draw would be well supported by the power supply.

Increasing the current limit of the power supply solved the problem. So I suspect the peak current rating of your USB battery bank. Check with another power source. Also, my experience with USB cables is there's a wide difference in cable quality (= resistance), which also could be detrimental to the initial current in-rush.

If possible, monitor input and output voltage from the regulator with an oscilloscope. The events the first 15 milliseconds were very revealing for me.

EDIT:


  Tried a few other USB batteries, some work, some don't


Then you already found a solution. I might have been able to contribute the 'why'.