You should also be "roughing up" the terminals and then cleaning them with something that doesn't leave any residue like motor spray or denat alcohol. Then its time for tinning and flux.

I use a dremel and cutting disc and very lightly make a pass over both + and - terminals - lightly so you can just see some abrasion. Motor spray and clean each as they go into soldering jig. Never have prob with anything not sticking or anything failing my pull on it test after soldering.