Because of the size of the starter/generator units fitted to the APU, a NiCad cannot produce sufficient current, no matter how big it is.
If the only reason they are clinging to Lithium Ion batteries is to get enough current to start the APU when there are no generators on line, they they should consider a cartridge starter. Cartridge starters will get a turbine up to speed in a real hurry. Reliable too.