I haven't had any trouble soldering to batteries in the past, but you can try an old soldering onto aluminum trick:

Rough up the surface with sandpaper, and put just a TINY bit of motor oil on the metal prior to soldering. (it can be used motor oil)

If that doesn't work then you should start worrying about how many times you're cooking the battery trying to solder to it.