IMHO, yes your iron is not hot enough to heat the wires. The wires are dissipating the heat faster than the iron can keep up. You can try separating the strands of the cable to give them less mass so they will heat up easier, but then you end up soldering a few strands at a time then using a mass of solder to "glue" the solder joints together. I've used that in a pinch, but its not a good idea, more time consuming, and more likely to fail over time.

Just get a decent iron. In a pinch a butane micro torch will also give you plenty more heat but harder to control.

I dont think flux is gonna help much. Better solder may be a good idea.