try wetting the tip with abit of solder before placing over the battery tabs.

it should conduct the heat better from soldering iron to the battery.

i am using a 60W soldering iron. never gave any problems

hope this helps